Submission #2140163
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 (Clang 3.8.0) |
Score | 400 |
Code Size | 4080 Byte |
Status | MLE |
Exec Time | 554 ms |
Memory | 826996 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | 0 / 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 | 12 ms | 11256 KB |
00_example_02.txt | AC | 4 ms | 10624 KB |
00_example_03.txt | AC | 4 ms | 10624 KB |
s1_01.txt | AC | 5 ms | 12032 KB |
s1_02.txt | AC | 5 ms | 11520 KB |
s1_03.txt | AC | 6 ms | 13952 KB |
s1_04.txt | AC | 4 ms | 10752 KB |
s1_05.txt | AC | 5 ms | 11392 KB |
s1_06.txt | AC | 9 ms | 18688 KB |
s1_07.txt | AC | 5 ms | 12800 KB |
s1_08.txt | AC | 6 ms | 11264 KB |
s1_09.txt | AC | 4 ms | 10752 KB |
s1_10.txt | AC | 7 ms | 14720 KB |
s1_11.txt | AC | 5 ms | 11648 KB |
s1_12.txt | AC | 6 ms | 13184 KB |
s1_13.txt | AC | 4 ms | 10752 KB |
s1_14.txt | AC | 7 ms | 14720 KB |
s1_15.txt | AC | 7 ms | 13952 KB |
s1_16.txt | AC | 8 ms | 16000 KB |
s1_17.txt | AC | 7 ms | 14720 KB |
s2_01.txt | AC | 37 ms | 45312 KB |
s2_02.txt | AC | 9 ms | 16128 KB |
s2_03.txt | AC | 331 ms | 359040 KB |
s2_04.txt | AC | 172 ms | 170624 KB |
s2_05.txt | AC | 277 ms | 236160 KB |
s2_06.txt | MLE | 473 ms | 514944 KB |
s2_07.txt | AC | 256 ms | 246144 KB |
s2_08.txt | AC | 113 ms | 105984 KB |
s2_09.txt | AC | 463 ms | 504576 KB |
s2_10.txt | AC | 311 ms | 298496 KB |
s2_11.txt | MLE | 554 ms | 826996 KB |
s2_12.txt | AC | 12 ms | 23680 KB |
s2_13.txt | AC | 267 ms | 76288 KB |
s2_14.txt | AC | 265 ms | 76288 KB |
s2_15.txt | AC | 238 ms | 69504 KB |
s2_16.txt | AC | 37 ms | 45440 KB |
s2_17.txt | AC | 10 ms | 17280 KB |
s2_18.txt | AC | 258 ms | 276736 KB |
s2_19.txt | AC | 159 ms | 170624 KB |
s2_20.txt | AC | 479 ms | 426240 KB |
s2_21.txt | AC | 443 ms | 354304 KB |
s2_22.txt | MLE | 533 ms | 553856 KB |
s2_23.txt | AC | 496 ms | 425984 KB |
s2_24.txt | AC | 308 ms | 158720 KB |
s2_25.txt | AC | 229 ms | 52608 KB |
s2_26.txt | AC | 215 ms | 35200 KB |
s2_27.txt | AC | 243 ms | 57472 KB |
s2_28.txt | AC | 248 ms | 54784 KB |
s2_29.txt | AC | 276 ms | 89984 KB |
s2_30.txt | AC | 276 ms | 90112 KB |
s2_31.txt | AC | 248 ms | 66304 KB |
s2_32.txt | AC | 250 ms | 66176 KB |