Submission #1015198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015198		parsadox2	Friend (IOI14_friend)	C++17	19 / 100	1 ms	4740 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n , ar[N] , dp[N][2];
bool par[N] , prv[N];
vector <int> adj[N];

void Dfs(int v)
{
	for(auto u : adj[v])
		Dfs(u);
	if(adj[v].empty())
	{
		dp[v][1] = ar[v];
		//cout << v << " : " << dp[v][0] << " " << dp[v][1] << endl;
		return;
	}
	int tmp[2];
	tmp[0] = tmp[1] = 0;
	for(auto u : adj[v])
	{
		if(prv[u])
			tmp[1] = max(tmp[1] + dp[u][0] , tmp[0] + dp[u][1]);
		else
			tmp[1] += dp[u][1];
		tmp[0] += dp[u][0];
	}
	dp[v][0] = tmp[1];
	tmp[0] = tmp[1] = ar[v];
	for(auto u : adj[v])
	{
		if(par[u])
			tmp[1] += dp[u][0];
		else if(prv[u])
			tmp[1] = max(tmp[1] + dp[u][0] , tmp[0] + dp[u][1]);
		else
			tmp[1] += dp[u][1];
		tmp[0] += dp[u][0];
	}
	dp[v][1] = max(dp[v][0] , tmp[1]);
	//cout << v << " : " << dp[v][0] << " " << dp[v][1] << endl;
}

int findSample(int nn,int confidence[],int host[],int protocol[]){
	n = nn;
	for(int i = 0 ; i < n ; i++)
		ar[i] = confidence[i];
	for(int i = 1 ; i < n ; i++)
	{
		adj[host[i]].push_back(i);
		if(protocol[i] == 0)
			par[i] = true;
		else if(protocol[i] == 1)
			prv[i] = true;
		else
		{
			par[i] = true;
			prv[i] = true;
		}
	}
	Dfs(0);
	return dp[0][1];
}

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