Submission #1872063


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];
	int las = 0;
	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]);
		las = tame[srt[i - 1].second].size();
	}
	vector<node>&res = tame[srt[srt.size() - 1].second];
	int cnt = 0;
	for (auto itr = res.rbegin(); itr != res.rend(); ++itr) {
		if (cnt >= las)break;
		LL zero = mpow(2, itr->sum) + MOD;
		zero = (zero - itr->one) % MOD;
		itr->nil = zero;
		cnt++;
	}
	res.push_back({ 1,1,1 });
	return 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]]++;
	}
	LL answer = 0;
	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;
		answer += kis;
		answer %= MOD;
	}
	cout << answer << endl;
	return 0;
}

Submission Info

Submission Time
Task E - Smuggling Marbles
User eiya
Language C++14 (Clang 3.8.0)
Score 400
Code Size 3200 Byte
Status
Exec Time 3159 ms
Memory 61936 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 0 / 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 5 ms 7680 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 11 ms 8312 KB
s1_09.txt 4 ms 7808 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 21 ms 7936 KB
s2_02.txt 7 ms 7680 KB
s2_03.txt 135 ms 9856 KB
s2_04.txt 89 ms 9088 KB
s2_05.txt 158 ms 10752 KB
s2_06.txt 202 ms 11008 KB
s2_07.txt 134 ms 9984 KB
s2_08.txt 67 ms 8832 KB
s2_09.txt 191 ms 10880 KB
s2_10.txt 162 ms 10496 KB
s2_11.txt 120 ms 23400 KB
s2_12.txt 5 ms 7808 KB
s2_13.txt 3159 ms 61936 KB
s2_14.txt 3159 ms 61916 KB
s2_15.txt 3158 ms 56628 KB
s2_16.txt 20 ms 7936 KB
s2_17.txt 6 ms 7680 KB
s2_18.txt 136 ms 10240 KB
s2_19.txt 84 ms 9088 KB
s2_20.txt 227 ms 12032 KB
s2_21.txt 268 ms 12544 KB
s2_22.txt 215 ms 11264 KB
s2_23.txt 237 ms 12032 KB
s2_24.txt 268 ms 14208 KB
s2_25.txt 298 ms 15716 KB
s2_26.txt 948 ms 18996 KB
s2_27.txt 3158 ms 46320 KB
s2_28.txt 3157 ms 44088 KB
s2_29.txt 3158 ms 59580 KB
s2_30.txt 3158 ms 59636 KB
s2_31.txt 3157 ms 38828 KB
s2_32.txt 3157 ms 38860 KB