Submission #582411

#	Time	Username	Problem	Language	Result	Execution time	Memory
582411		wdjpng	Friend (IOI14_friend)	C++17	35 / 100	3 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  mem[allow][v]=max(s2,s);
	return mem[allow][v]=s;
}
// Find out best sample
signed findSample(signed n,signed oorgconf[],signed host[],signed protocol[]){
	vector<int>ops;
	rep(i,n-1) ops.push_back(protocol[i+1]);
	sort(all(ops));
	ops.erase(unique(all(ops)), ops.end());

	vector<int>without(n,0);
	E.assign(n, vector<int>());
	rep(i,n) conf[i]=oorgconf[i];

	if(ops.size()==1)
	{
		int sum=0, maxx=0;
		rep(i,n) maxx=max(maxx,conf[i]);
		for(int x : conf) sum+=x;

		if(ops[0]==1) // my friends are yours
		{
			return sum;
		}
		if(ops[2]) return maxx;
	}

	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:52:6: warning: unused variable 'best' [-Wunused-variable]
   52 |  int best = conf[0];
      |      ^~~~

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