Submission #1066273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066273		Mardonbekhazratov	Friend (IOI14_friend)	C++17	35 / 100	1 ms	600 KiB

friend

#include "friend.h"
#include <algorithm>
#include <vector>

// Find out best sample

std::vector<std::vector<int>>v,dp;
std::vector<int>a;

int ans=0;

void dfs(int x,int p){
	dp[x][1]=a[x];
	for(int z:v[x]){
		if(z!=p){
			dfs(z,x);
			dp[x][0]+=std::max(dp[z][1],dp[z][0]);
			dp[x][1]+=dp[z][0];
		}
	}
}

int sub4(int n,int confidence[],int host[]){
	v.resize(n);
	a.resize(n);
	dp.assign(n,std::vector<int>(2,0));
	for(int i=0;i<n;i++) a[i]=confidence[i];
	for(int i=1;i<n;i++){
		v[i].push_back(host[i]);
		v[host[i]].push_back(i);
	}
	dfs(0,0);
	return std::max(dp[0][0],dp[0][1]);
}

int findSample(int n,int confidence[],int host[],int protocol[]){
	if(protocol[1]==0) return sub4(n,confidence,host);
	for(int i=0;i<n;i++) ans=(protocol[1]&1 ? ans+confidence[i] : std::max(ans,confidence[i]));
	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