Submission #2140155
Source Code Expand
/** * File : E.cpp * Author : Kazune Takahashi * Created : 2018-2-27 14:50:03 * Powered by Visual Studio Code */ #include <iostream> #include <iomanip> // << fixed << setprecision(xxx) #include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ; #include <vector> #include <string> // to_string(nnn) // substr(m, n) // stoi(nnn) #include <complex> #include <tuple> #include <queue> #include <stack> #include <map> // if (M.find(key) != M.end()) { } #include <set> #include <random> // random_device rd; mt19937 mt(rd()); #include <cctype> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> using namespace std; #define DEBUG 0 // change 0 -> 1 if we need debug. typedef long long ll; // const int dx[4] = {1, 0, -1, 0}; // const int dy[4] = {0, 1, 0, -1}; // const int C = 1e6+10; const int MAX_SIZE = 1000010; const long long MOD = 1000000007; long long inv[MAX_SIZE]; long long fact[MAX_SIZE]; long long factinv[MAX_SIZE]; void init() { inv[1] = 1; for (int i=2; i<MAX_SIZE; i++) { inv[i] = ((MOD - inv[MOD%i]) * (MOD/i))%MOD; } fact[0] = factinv[0] = 1; for (int i=1; i<MAX_SIZE; i++) { fact[i] = (i * fact[i-1])%MOD; factinv[i] = (inv[i] * factinv[i-1])%MOD; } } long long C(int n, int k) { if (n >=0 && k >= 0 && n-k >= 0) { return ((fact[n] * factinv[k])%MOD * factinv[n-k])%MOD; } return 0; } long long power(long long x, long long n) { if (n == 0) { return 1; } else if (n%2 == 1) { return (x * power(x, n-1)) % MOD; } else { long long half = power(x, n/2); return (half * half) % MOD; } } long long gcm(long long a, long long b) { if (a < b) { return gcm(b, a); } if (b == 0) return a; return gcm(b, a%b); } int N; int parent[200010]; vector<int> children[200010]; int depth[200010]; ll dep[200010]; vector<deque<vector<ll>>> DP; vector<deque<vector<ll>>>::iterator itr[200010]; vector<ll> first = {1, 1, 0}; vector<deque<vector<ll>>>::iterator make(int v) { if (children[v].empty()) { DP[v].push_front(first); itr[v] = DP.begin() + v; return itr[v]; } auto it = make(children[v][0]); int len = 0; for (auto i = 1; i < (int)children[v].size(); i++) { auto tit = make(children[v][i]); if (it->size() < tit->size()) swap(it, tit); len = max(len, (int)(tit->size())); for (auto j = 0; j < (int)(tit->size()); j++) { ll zero = ((*it)[j][0] * (*tit)[j][0]) % MOD; ll one = ((*it)[j][1] * (*tit)[j][0]) % MOD; one += ((*it)[j][0] * (*tit)[j][1]) % MOD; one %= MOD; ll sum1 = ((*it)[j][0] + (*it)[j][1] + (*it)[j][2]) % MOD; ll sum2 = ((*tit)[j][0] + (*tit)[j][1] + (*tit)[j][2]) % MOD; ll two = ((sum1 * sum2) % MOD + MOD - zero + MOD - one) % MOD; (*it)[j][0] = zero; (*it)[j][1] = one; (*it)[j][2] = two; } tit->clear(); } for (auto i = 0; i < len; i++) { (*it)[i][0] += (*it)[i][2]; (*it)[i][0] %= MOD; (*it)[i][2] = 0; } (*it).push_front(first); itr[v] = it; return itr[v]; } int main() { cin >> N; parent[0] = -1; for (auto i = 1; i <= N; i++) { cin >> parent[i]; children[parent[i]].push_back(i); } DP = vector<deque<vector<ll>>>(N + 1); depth[0] = 0; queue<int> Q; Q.push(0); while (!Q.empty()) { int now = Q.front(); Q.pop(); for (auto x : children[now]) { depth[x] = depth[now] + 1; #if DEBUG == 1 //cerr << "depth[" << x << "] = " << depth[x] << endl; #endif Q.push(x); } } for (auto i = 0; i < N + 1; i++) { dep[depth[i]]++; } auto ans = *make(0); ll res = 0; for (auto i = 0; i < (int)ans.size(); i++) { #if DEBUG == 1 cerr << "ans[" << i << "][1] = " << ans[i][1] << ", dep[" << i << "] = " << dep[i] << endl; #endif res += (ans[i][1] * power(2, N + 1 - dep[i])) % MOD; res %= MOD; } cout << res << endl; }
Submission Info
Submission Time | |
---|---|
Task | E - Smuggling Marbles |
User | kazunetakahashi |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 4080 Byte |
Status | AC |
Exec Time | 281 ms |
Memory | 223232 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 | 3 ms | 8448 KB |
00_example_02.txt | AC | 3 ms | 8448 KB |
00_example_03.txt | AC | 3 ms | 8448 KB |
s1_01.txt | AC | 4 ms | 8960 KB |
s1_02.txt | AC | 4 ms | 8832 KB |
s1_03.txt | AC | 4 ms | 9216 KB |
s1_04.txt | AC | 3 ms | 8448 KB |
s1_05.txt | AC | 4 ms | 8832 KB |
s1_06.txt | AC | 5 ms | 9728 KB |
s1_07.txt | AC | 4 ms | 8832 KB |
s1_08.txt | AC | 5 ms | 10624 KB |
s1_09.txt | AC | 4 ms | 8960 KB |
s1_10.txt | AC | 5 ms | 9856 KB |
s1_11.txt | AC | 4 ms | 8832 KB |
s1_12.txt | AC | 4 ms | 9344 KB |
s1_13.txt | AC | 3 ms | 8448 KB |
s1_14.txt | AC | 5 ms | 9856 KB |
s1_15.txt | AC | 5 ms | 9856 KB |
s1_16.txt | AC | 5 ms | 9856 KB |
s1_17.txt | AC | 5 ms | 9856 KB |
s2_01.txt | AC | 18 ms | 19840 KB |
s2_02.txt | AC | 6 ms | 10624 KB |
s2_03.txt | AC | 170 ms | 95232 KB |
s2_04.txt | AC | 97 ms | 60928 KB |
s2_05.txt | AC | 167 ms | 98432 KB |
s2_06.txt | AC | 251 ms | 134400 KB |
s2_07.txt | AC | 144 ms | 85760 KB |
s2_08.txt | AC | 69 ms | 46336 KB |
s2_09.txt | AC | 251 ms | 131712 KB |
s2_10.txt | AC | 183 ms | 102656 KB |
s2_11.txt | AC | 149 ms | 142836 KB |
s2_12.txt | AC | 5 ms | 10624 KB |
s2_13.txt | AC | 248 ms | 223232 KB |
s2_14.txt | AC | 247 ms | 223232 KB |
s2_15.txt | AC | 222 ms | 201344 KB |
s2_16.txt | AC | 17 ms | 19840 KB |
s2_17.txt | AC | 6 ms | 10624 KB |
s2_18.txt | AC | 122 ms | 95744 KB |
s2_19.txt | AC | 75 ms | 60928 KB |
s2_20.txt | AC | 281 ms | 144640 KB |
s2_21.txt | AC | 271 ms | 145024 KB |
s2_22.txt | AC | 272 ms | 144000 KB |
s2_23.txt | AC | 274 ms | 144640 KB |
s2_24.txt | AC | 229 ms | 146816 KB |
s2_25.txt | AC | 191 ms | 148608 KB |
s2_26.txt | AC | 196 ms | 152320 KB |
s2_27.txt | AC | 234 ms | 194944 KB |
s2_28.txt | AC | 228 ms | 190848 KB |
s2_29.txt | AC | 247 ms | 219392 KB |
s2_30.txt | AC | 250 ms | 219392 KB |
s2_31.txt | AC | 229 ms | 183680 KB |
s2_32.txt | AC | 228 ms | 183680 KB |