Submission #20208148


Source Code Expand

Copy
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>

using namespace std;

typedef long long ll;

int N;
vector<vector<int>> E;
vector<int> parent;

int sub_tree_size[100000 + 10];
int depth_from_here[100000 + 10];//depth_from_here[i] := 頂点iから延びる先が一本道の場合、その深さ+1

int dp[100000 + 10];//dp[i] := 頂点iにいるときの行先を決められる人(つまりiでのコインをもらえない人)が適切に行先を選んだ時、自分が得られるコイン-相手が得られるコインの最大値

void dfsForSize(int now, int bef, int start, int depth) {
	sub_tree_size[now] = 1;
	for (int i = 0; i < E[now].size(); i++) {
		int nxt = E[now][i];
		if (nxt == bef)continue;
		if (E[now].size() >= 2) {
			dfsForSize(nxt, now, nxt, 0);
		}
		else if(E[now].size() == 1){
			dfsForSize(nxt, now, start, depth + 1);
		}
		sub_tree_size[now] += sub_tree_size[nxt];
	}
	if (E[now].size() == 0) {
		depth_from_here[start] = depth + 1;
	}
}

void dfs_dp(int now, int bef) {
	vector<pair<int, int>> change, unchange;//<X, 子の頂点番号> 子のうち、手番を相手に渡すものと渡さないもの。 Xは自分の利益-相手の利益
	dp[now] = -1;//今の頂点のコインは取られるため
	for (int i = 0; i < E[now].size(); i++) {
		int nxt = E[now][i];
		if (depth_from_here[nxt] != 0) {
			//この子は一本道
			dp[nxt] = 0;//nxtで操作権を持つ人は1コインももらえない
			if (sub_tree_size[nxt] % 2) {
				//手番を相手に渡す
				dp[nxt] = 0;
				change.push_back(make_pair(-depth_from_here[nxt], nxt));
			}
			else {
				//手番は自分のまま(この場合だとひたすらに自分が損)
				dp[nxt] = 0;
				unchange.push_back(make_pair(-depth_from_here[nxt], nxt));
			}
		}
		else {
			//この子は一本道に直結しない
			dfs_dp(nxt, now);
			if (sub_tree_size[nxt] % 2)
				change.push_back(make_pair(dp[nxt], nxt));
			else 
				unchange.push_back(make_pair(dp[nxt], nxt));
		}
	}

	sort(change.begin(), change.end());
	sort(unchange.begin(), unchange.end());

	//まずはunchageでプラスのやつを取れるだけ取る
	while (unchange.size() && unchange.back().first > 0)
		dp[now] += unchange.back().first, unchange.pop_back();
	//changeでプラスのやつを交互に取る。
	bool toggle = (change.size() % 2);//falseなら相変わらず自分の手番で、unchangedを全部自分が消化 trueなら相手が消化
	for (int i = change.size() - 1; i >= 0; i -= 2) {
		dp[now] += change[i].first;//自分がとるので
		if (i - 1 >= 0) {
			dp[now] -= change[i - 1].first;//相手が取るので
		}
	}
	if (!toggle) {
		//自分で全部消化することに...
		while (unchange.size())
			dp[now] +=unchange.back().first, unchange.pop_back();
	}
	else {
		//相手で全部消化することに!!!
		while (unchange.size())
			dp[now] -= unchange.back().first, unchange.pop_back();
	}
}

int main() {
	cin >> N;
	parent.resize(N);
	E.resize(N);
	parent[0] = -1;
	for (int i = 1; i < N; i++) {
		int p;
		cin >> p;
		p--;
		E[p].push_back(i);
		parent[i] = p;
	}
	//各部分木のサイズと、枝分かれの深さを計算。
	dfsForSize(0, -1, 0, 0);

	if (depth_from_here[0] != 0) {
		//一本道なら
		cout << N << endl;
	}
	else {
		dfs_dp(0, -1);
		cout << (N - dp[0]) / 2 << endl;
	}

	return 0;
}

Submission Info

Submission Time
Task C - DFS Game
User Sen
Language C++ (GCC 9.2.1)
Score 500
Code Size 3491 Byte
Status AC
Exec Time 50 ms
Memory 18660 KB

Compile Error

./Main.cpp: In function ‘void dfsForSize(int, int, int, int)’:
./Main.cpp:21:20: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   21 |  for (int i = 0; i < E[now].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
./Main.cpp: In function ‘void dfs_dp(int, int)’:
./Main.cpp:40:20: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   40 |  for (int i = 0; i < E[now].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
./Main.cpp:37:26: warning: unused parameter ‘bef’ [-Wunused-parameter]
   37 | void dfs_dp(int now, int bef) {
      |                      ~~~~^~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 34
Set Name Test Cases
Sample sample.txt, sample_2.txt, sample_3.txt
All contract_10.txt, contract_10_2.txt, contract_10_3.txt, contract_10_4.txt, contract_2.txt, contract_2_2.txt, contract_2_3.txt, contract_2_4.txt, contract_3000.txt, contract_3000_2.txt, contract_3000_3.txt, contract_3000_4.txt, contract_500.txt, contract_500_2.txt, contract_500_3.txt, contract_500_4.txt, lucky.txt, min.txt, random.txt, random_10.txt, random_2.txt, random_3.txt, random_4.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample.txt, sample_2.txt, sample_3.txt, uni.txt, unlucky.txt, unu.txt
Case Name Status Exec Time Memory
contract_10.txt AC 44 ms 9488 KB
contract_10_2.txt AC 41 ms 10052 KB
contract_10_3.txt AC 42 ms 9484 KB
contract_10_4.txt AC 44 ms 10088 KB
contract_2.txt AC 46 ms 9176 KB
contract_2_2.txt AC 46 ms 9344 KB
contract_2_3.txt AC 45 ms 8956 KB
contract_2_4.txt AC 46 ms 9256 KB
contract_3000.txt AC 42 ms 12400 KB
contract_3000_2.txt AC 43 ms 12144 KB
contract_3000_3.txt AC 39 ms 10808 KB
contract_3000_4.txt AC 44 ms 11408 KB
contract_500.txt AC 44 ms 10760 KB
contract_500_2.txt AC 40 ms 10088 KB
contract_500_3.txt AC 38 ms 10488 KB
contract_500_4.txt AC 41 ms 10208 KB
lucky.txt AC 47 ms 18580 KB
min.txt AC 2 ms 3480 KB
random.txt AC 23 ms 4724 KB
random_10.txt AC 50 ms 8388 KB
random_2.txt AC 34 ms 6304 KB
random_3.txt AC 7 ms 3800 KB
random_4.txt AC 46 ms 8384 KB
random_5.txt AC 19 ms 5052 KB
random_6.txt AC 23 ms 5312 KB
random_7.txt AC 17 ms 4116 KB
random_8.txt AC 18 ms 4392 KB
random_9.txt AC 47 ms 8100 KB
sample.txt AC 2 ms 3452 KB
sample_2.txt AC 2 ms 3476 KB
sample_3.txt AC 2 ms 3616 KB
uni.txt AC 36 ms 8440 KB
unlucky.txt AC 48 ms 18660 KB
unu.txt AC 45 ms 9432 KB