Submission #3715959
Source Code Expand
#include <vector> #include <iostream> #include <algorithm> #include <utility> #include <deque> using namespace std; using Graph = vector< vector<int> >; using ll = long long int; int cnt_depth[200010], pow2[200010]; const ll MOD = 1000000007; struct Node { ll a, b, c; Node() { a = b = c = 0; } Node(ll x, ll y, ll z) : a(x), b(y), c(z) {} }; Node merge(Node lhs, Node rhs) { Node res; res.a = (lhs.a * rhs.a) % MOD; res.b = ((lhs.a * rhs.b) % MOD + (lhs.b * rhs.a) % MOD) % MOD; res.c = 0; (res.c += lhs.c * (rhs.a + rhs.b + rhs.c)) %= MOD; (res.c += lhs.b * (rhs.b + rhs.c)) %= MOD; (res.c += lhs.a * rhs.c) %= MOD; return res; } deque<Node> solve(Graph &G, int cur, int depth=0) { cnt_depth[depth]++; deque<Node> res; int sz = 0; for(auto to : G[cur]) { auto nxt = solve(G, to, depth + 1); if(res.size() < nxt.size()) swap(res, nxt); for(size_t i=0; i<nxt.size(); i++) { res[i] = merge(res[i], nxt[i]); } sz = max<int>(sz, nxt.size()); } for(int i=0; i<sz; i++) { (res[i].a += res[i].c) %= MOD; res[i].c = 0; } res.push_front(Node(1, 1, 0)); return res; } int main() { ll N, ans = 0; cin >> N; Graph G(N+1); pow2[0] = 1, pow2[1] = 2; for(int i=1; i<=N; i++) { int par; cin >> par; G[par].push_back(i); pow2[i+1] = (pow2[i] * 2) % MOD; } auto deq = solve(G, 0); for(size_t i=0; i<deq.size(); i++) { (ans += deq[i].b * pow2[N + 1 - cnt_depth[i]]) %= MOD; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Smuggling Marbles |
User | tsutaj |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 1709 Byte |
Status | AC |
Exec Time | 193 ms |
Memory | 178304 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | 600 / 600 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt, s2_01.txt, s2_02.txt, s2_03.txt, s2_04.txt, s2_05.txt, s2_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt, s2_29.txt, s2_30.txt, s2_31.txt, s2_32.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 1 ms | 256 KB |
00_example_02.txt | AC | 1 ms | 256 KB |
00_example_03.txt | AC | 1 ms | 256 KB |
s1_01.txt | AC | 2 ms | 256 KB |
s1_02.txt | AC | 2 ms | 256 KB |
s1_03.txt | AC | 2 ms | 256 KB |
s1_04.txt | AC | 1 ms | 256 KB |
s1_05.txt | AC | 2 ms | 256 KB |
s1_06.txt | AC | 2 ms | 384 KB |
s1_07.txt | AC | 2 ms | 256 KB |
s1_08.txt | AC | 3 ms | 2048 KB |
s1_09.txt | AC | 2 ms | 768 KB |
s1_10.txt | AC | 2 ms | 384 KB |
s1_11.txt | AC | 2 ms | 256 KB |
s1_12.txt | AC | 2 ms | 256 KB |
s1_13.txt | AC | 1 ms | 256 KB |
s1_14.txt | AC | 2 ms | 384 KB |
s1_15.txt | AC | 2 ms | 384 KB |
s1_16.txt | AC | 2 ms | 384 KB |
s1_17.txt | AC | 2 ms | 384 KB |
s2_01.txt | AC | 10 ms | 1024 KB |
s2_02.txt | AC | 3 ms | 384 KB |
s2_03.txt | AC | 68 ms | 5376 KB |
s2_04.txt | AC | 42 ms | 3584 KB |
s2_05.txt | AC | 72 ms | 6400 KB |
s2_06.txt | AC | 98 ms | 7680 KB |
s2_07.txt | AC | 62 ms | 5248 KB |
s2_08.txt | AC | 32 ms | 2816 KB |
s2_09.txt | AC | 97 ms | 7424 KB |
s2_10.txt | AC | 76 ms | 6272 KB |
s2_11.txt | AC | 81 ms | 6648 KB |
s2_12.txt | AC | 3 ms | 384 KB |
s2_13.txt | AC | 193 ms | 178304 KB |
s2_14.txt | AC | 192 ms | 178304 KB |
s2_15.txt | AC | 172 ms | 160128 KB |
s2_16.txt | AC | 10 ms | 1024 KB |
s2_17.txt | AC | 3 ms | 384 KB |
s2_18.txt | AC | 68 ms | 5760 KB |
s2_19.txt | AC | 41 ms | 3584 KB |
s2_20.txt | AC | 111 ms | 8960 KB |
s2_21.txt | AC | 119 ms | 9472 KB |
s2_22.txt | AC | 104 ms | 8192 KB |
s2_23.txt | AC | 110 ms | 8960 KB |
s2_24.txt | AC | 108 ms | 11520 KB |
s2_25.txt | AC | 103 ms | 14080 KB |
s2_26.txt | AC | 110 ms | 22400 KB |
s2_27.txt | AC | 161 ms | 116608 KB |
s2_28.txt | AC | 157 ms | 107264 KB |
s2_29.txt | AC | 187 ms | 169984 KB |
s2_30.txt | AC | 188 ms | 169984 KB |
s2_31.txt | AC | 172 ms | 93312 KB |
s2_32.txt | AC | 165 ms | 93312 KB |