Submission #1248414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248414		Dedibeat	Friend (IOI14_friend)	C++20	35 / 100	1 ms	328 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
pair<int, int> dfs(int v, vector<int> adj[], int val[])
{
	int pick = val[v], no_pick = 0;
	for(int u : adj[v])
	{
		auto [x1, x2] = dfs(u, adj, val);
		pick += x2;
		no_pick += x1;
	}
	return make_pair(max(pick, no_pick), no_pick);
}

int findSample(int n,int conf[],int host[],int prot[]){
	vector<int> adj[n];
	int head[n], sub_head[n];
	head[0] = 0; sub_head[0] = 0;
	for(int i = 1; i < n; i++)
	{
		int p = host[i];
		//cout << "par " << p << " head " << head[p] << endl;
		if(prot[i] == 0)
		{
			adj[head[p]].push_back(i);
			head[i] = i;
			sub_head[i] = i;
		}
		else if(prot[i] == 1)
		{
			head[i] = head[p];
			sub_head[i] = i;
		}
		else 
		{
			head[i] = head[p];
			sub_head[i] = sub_head[p];
		}

		//cout << i << " " << head[i] << ' ' << sub_head[i] << endl;
	}


	// for(int i = 0; i < n; i++)
	// {
	// 	cout << prot[i] << endl;
	// }
	
	for(int i = 0; i < n; i++)
	{
		int h = sub_head[i];
		//cout << "head " << h << endl;
		if(i == h) continue;
		conf[h] = max(conf[h], conf[i]);
	}

	for(int i = 0; i < n; i++)
	{
		int h = head[i];
		//cout << "head " << h << endl;
		if(i == h) continue;
		if(sub_head[i] != i) continue;
		conf[h] = conf[h] + conf[i];
	}

	// for(int i = 0; i < n; i++)
	// {
	// 	cout << conf[i] << endl;
	// }

	auto [ans, _] = dfs(0, adj, conf);
	return ans;
}

• Subtask 1: 0 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31