Submission #404182

#	Time	Username	Problem	Language	Result	Execution time	Memory
404182		Kenzo_1114	Friend (IOI14_friend)	C++17	8 / 100	3 ms	2636 KiB

friend

#include<bits/stdc++.h>
#include"friend.h"
using namespace std;
const int MAXN = 100010;

int n, c[MAXN], h[MAXN], p[MAXN];

/*
	0 : IAmYourFriend
	1 : MyFriendsAreYourFriends
	2 : WeAreYourFriends
*/

int task2()
{
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		if(p[i] != 1)	return 0;
		ans += c[i];
	}

	return ans;
}

int task3()
{
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		if(p[i] != 2)	return 0;
		ans = max(ans, c[i]);
	}

	return ans;
}
	
int dp[2][MAXN];
vector<int> graph[MAXN];

int dfs4(int v, int p)
{
	dp[1][v] = c[v];

	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		if(u == p)	continue;

		dp[0][v] += dfs4(u, v);
		dp[1][v] += dp[0][u];
	}

	return max(dp[0][v], dp[1][v]);
}

int task4()
{
	int ans = 0;
	for(int i = 0; i < n; i++)
		if(p[i] != 0)	return 0;

	for(int i = 1; i < n; i++)
	{
		int a = h[i];
		int b = i;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	return dfs4(0, 0);
}

int color[MAXN];

int task5()
{
	for(int i = 1; i < n; i++)
	{
		int a = h[i];
		int b = i;

		if(p[i] == 0)	color[b] = !color[a];
		else	color[b] = color[a];	
	}	

	int ans[2] = {0, 0};
	for(int i = 0; i < n; i++)
		ans[color[i]] += c[i];

	return max(ans[0], ans[1]);
}

int findSample(int N, int Confidence[], int Host[], int Protocol[])
{
	n = N;
	for(int i = 0; i < N; i++)	c[i] = Confidence[i];
	for(int i = 0; i < N; i++)	h[i] = Host[i];
	for(int i = 0; i < N; i++)	p[i] = Protocol[i];

	if(task2())	return task2();
	if(task3())	return task3();
	if(task4())	return task4();

	return task5();
}

Compilation message (stderr)

friend.cpp: In function 'int task4()':
friend.cpp:59:6: warning: unused variable 'ans' [-Wunused-variable]
   59 |  int ans = 0;
      |      ^~~

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