Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #1872057

Source Code Expand

Copy
```#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long int;

const LL MOD = 1000000007;

LL mpow(LL a, LL x) {
if (x == 0)return 1;
LL half = mpow(a, x / 2);
half *= half;
half %= MOD;
if (x % 2) {
half *= a;
half %= MOD;
}
return half;
}

int N;
int par[222222];
vector<int>child[222222];
int vnum[222222];
int cnt[222222];
int dep[222222];

void dfs(int v, int cou) {
dep[v] = cou;
for (int ch : child[v]) {
dfs(ch, cou + 1);
}
}

struct node {
LL nil, one;
LL sum;
};

node operator+(const node&n1, const node&n2) {
LL nil = (n1.nil * n2.nil) % MOD;
LL one = (n1.nil * n2.one + n1.one * n2.nil) % MOD;
return {
nil,one,n1.sum + n2.sum
};
}

void merge(vector<node> &prime, vector<node> &brnch) {
assert(prime.size() >= brnch.size());
int diff = prime.size() - brnch.size();
for (int i = 0; i < brnch.size(); ++i) {
node grow = prime[i + diff] + brnch[i];
prime[i + diff] = grow;
}
}

//yes,no
vector<node> dp(int v) {
if (child[v].empty()) {
return vector<node>(1, { 1,1,1 });
}
/*
vector<node>res = dp(child[v][0]);

for (int i = 1; i < child[v].size(); ++i) {
vector<node>tmp = dp(child[v][i]);
if (tmp.size() > res.size()) {
merge(tmp, res);
//res = move(tmp);
swap(res, tmp);
}
else {
merge(res, tmp);
}
}
*/
vector<pair<int, int>>srt;
vector<vector<node>>tame;
for (int ch : child[v]) {
tame.emplace_back(dp(ch));
srt.push_back({ tame.back().size(),tame.size() - 1 });
}
sort(srt.begin(), srt.end());
//vector<node>&res = tame[srt[0].second];
for (int i = 1; i < srt.size(); ++i) {
//vector<node>&tmp = tame[srt[i].second];
/*
if (tmp.size() > res.size()) {
merge(tmp, res);
res = move(tmp);
//swap(res, tmp);
}
else {
merge(res, tmp);
}
*/
merge(tame[srt[i].second], tame[srt[i - 1].second]);
}
vector<node>&res = tame[srt[srt.size() - 1].second];
for (int i = res.size()-((srt.size()>=2)?
(tame[srt[srt.size() - 2].second].size()):0);
i < res.size();++i) {
auto& n = res[i];
LL zero = mpow(2, n.sum) + MOD;
zero = (zero - n.one) % MOD;
n.nil = zero;
}
res.push_back({ 1,1,1 });
return std::move(res);
}

int main(void)
{
cin >> N;
for (int i = 0; i < N; ++i) {
cin >> par[1 + i];
child[par[1 + i]].push_back(i + 1);
}
dfs(0, 0);
vector<node> ans = dp(0);
for (int i = 0; i <= N; ++i) {
cnt[dep[i]]++;
}
for (int i = 0; i < ans.size(); ++i) {
LL kis = N + 1 - cnt[ans.size() - 1 - i];
kis = mpow(2, kis);
kis *= ans[i].one;
kis %= MOD;
}
return 0;
}
```

#### Submission Info

Submission Time 2017-12-15 15:54:14+0900 E - Smuggling Marbles eiya C++14 (Clang 3.8.0) 1000 3226 Byte AC 251 ms 66928 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
Subtask1 400 / 400 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 600 / 600 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 4 ms 7676 KB
00_example_02.txt 3 ms 7552 KB
00_example_03.txt 3 ms 7552 KB
s1_01.txt 4 ms 7552 KB
s1_02.txt 4 ms 7552 KB
s1_03.txt 4 ms 7552 KB
s1_04.txt 3 ms 7552 KB
s1_05.txt 4 ms 7552 KB
s1_06.txt 4 ms 7680 KB
s1_07.txt 4 ms 7680 KB
s1_08.txt 5 ms 8192 KB
s1_09.txt 4 ms 7680 KB
s1_10.txt 5 ms 7552 KB
s1_11.txt 4 ms 7552 KB
s1_12.txt 4 ms 7552 KB
s1_13.txt 3 ms 7552 KB
s1_14.txt 5 ms 7552 KB
s1_15.txt 5 ms 7680 KB
s1_16.txt 5 ms 7552 KB
s1_17.txt 5 ms 7552 KB
s2_01.txt 20 ms 7936 KB
s2_02.txt 6 ms 7680 KB
s2_03.txt 130 ms 9856 KB
s2_04.txt 83 ms 9088 KB
s2_05.txt 145 ms 10752 KB
s2_06.txt 192 ms 11008 KB
s2_07.txt 121 ms 9984 KB
s2_08.txt 62 ms 8832 KB
s2_09.txt 186 ms 10880 KB
s2_10.txt 149 ms 10496 KB
s2_11.txt 117 ms 22632 KB
s2_12.txt 5 ms 7808 KB
s2_13.txt 250 ms 66928 KB
s2_14.txt 251 ms 65648 KB
s2_15.txt 225 ms 60016 KB
s2_16.txt 19 ms 7936 KB
s2_17.txt 6 ms 7680 KB
s2_18.txt 127 ms 10240 KB
s2_19.txt 78 ms 9088 KB
s2_20.txt 219 ms 12032 KB
s2_21.txt 230 ms 12544 KB
s2_22.txt 205 ms 11264 KB
s2_23.txt 216 ms 12032 KB
s2_24.txt 223 ms 14208 KB
s2_25.txt 209 ms 15744 KB
s2_26.txt 209 ms 18572 KB
s2_27.txt 235 ms 46188 KB
s2_28.txt 231 ms 44640 KB
s2_29.txt 251 ms 63476 KB
s2_30.txt 251 ms 63596 KB
s2_31.txt 232 ms 43760 KB
s2_32.txt 235 ms 43120 KB