Submission #582395

#	Time	Username	Problem	Language	Result	Execution time	Memory
582395		wdjpng	Friend (IOI14_friend)	C++17	0 / 100	1079 ms	2756 KiB

friend

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

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()

using namespace std;
int N =1e5+1;

vector<vector<int>>mem(2,vector<int>(N,-1));
vector<vector<int>>E;
vector<int>conf(N);

int dfs(int v, int p, int allow)
{
	if(mem[allow][v]!=-1) return mem[allow][v];

	int s = 0;
	for (int w : E[v]) if(w!=p) s+=dfs(w,v,true);

	int s2=conf[v];
	for (int w : E[v]) if(w!=p) s2+=dfs(w,v,false);

	if(allow) return max(s2,s);
	return s;
}
// Find out best sample
signed findSample(signed n,signed oorgconf[],signed host[],signed protocol[]){
	vector<int>without(n,0);
	E.assign(n, vector<int>());
	rep(i,n) conf[i]=oorgconf[i];

	int best = conf[0];
	for(int st = 1; st < n; st++)
	{
		if(protocol[st]==0)
		{
			// I am friend
			E[host[st]].push_back(st);
		}
	}

	return dfs(0,-1,true);
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:34:6: warning: unused variable 'best' [-Wunused-variable]
   34 |  int best = conf[0];
      |      ^~~~

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