提出 #1872057


ソースコード 拡げる

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]]++;
	}
	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;
}

提出情報

提出日時
問題 E - Smuggling Marbles
ユーザ eiya
言語 C++14 (Clang 3.8.0)
得点 1000
コード長 3226 Byte
結果
実行時間 251 ms
メモリ 66928 KB

ジャッジ結果

セット名 得点 / 配点 テストケース
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
ケース名 結果 実行時間 メモリ
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