Submission #278773

#	Time	Username	Problem	Language	Result	Execution time	Memory
278773		amiratou	Friend (IOI14_friend)	C++14	46 / 100	41 ms	9720 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

set<int> adj[100005];
ll dp[100005][2],conf[100005],color[100005],N;
int prot[100005],ho[100005];
bool flag0,flag1,flag2,flag3;
// Find out best sample
void solve(int node,int p){
	dp[node][1]=conf[node];
	for(auto it:adj[node]){
		if(it==p)continue;
		solve(it,node);
		dp[node][0]+=max(dp[it][0],dp[it][1]);
		dp[node][1]+=dp[it][0];
	}
}
void construct(){
	for (int i = 1; i < N; ++i)
	{
		if(prot[i]==0){
			adj[ho[i]].insert(i);
			adj[i].insert(ho[i]);
		}
		else if(prot[i]==1){
			for(auto it:adj[ho[i]])
				adj[i].insert(it),adj[it].insert(i);
		}
		else{
			adj[ho[i]].insert(i);
			adj[i].insert(ho[i]);
			for(auto it:adj[ho[i]])
				adj[i].insert(it),adj[it].insert(i);	
		}
	}
}

int findSample(int n,int confidence[],int host[],int protocol[]){
	N=n;
	color[0]=-1,conf[0]=confidence[0];
	if(conf[0]!=1)flag3=1;
	for (int i = 1; i < n; ++i)
	{
		prot[i]=protocol[i];
		ho[i]=host[i];
		color[i]=-1;
		conf[i]=confidence[i];
		if(conf[i]!=1)flag3=1;
		if(protocol[i]==0)
			flag0=1;
		else if(protocol[i]==1)
			flag1=1;
		else flag2=1;
	}
	ll ans=0;
	if(n<=10){
		construct();
		for (int mask = 0; mask < (1<<n); ++mask)
		{
			vector<int> vec;
			ll sum=0;
			bool f=1;
			for (int j = 0; j < n; ++j)
			{
				if((mask>>j) &1){
					for(auto it:vec)
						if(adj[it].find(j)!=adj[it].end()){f=0;break;}
					if(!f)break;
					sum+=confidence[j],vec.push_back(j);
				}
			}
			if(f)ans=max(ans,sum);
		}
	}
	else if(!flag0 && !flag1){
		for (int i = 0; i < n; ++i)
			ans=max(ans,(ll)confidence[i]);
	}	
	else if(!flag0 && !flag2){
		for (int i = 0; i < n; ++i)
			ans+=confidence[i];
	}
	else if(!flag1 && !flag2){
		construct();
		solve(0,0);
		ans=max(dp[0][0],dp[0][1]);
	}
	else if(!flag2 && !flag3){
		construct();
		for (int i = 0; i < n; ++i)
			if(color[i]==-1){
				//cerr<<i<<"\n";
				int a=0,b=0;
				queue<int> q;
				q.push(i);
				color[i]=0;
				while(!q.empty()){
					int f=q.front();
					q.pop();
					if(!color[f])a++;
					else b++;
					for(auto it:adj[f]){
						if(color[it]!=-1)assert(color[it]!=color[f]);
						else color[it]=1-color[f],q.push(it);
					}
				}
				//cerr<<a<<","<<b<<"\n";
				ans+=max(a,b);
			}
	}
	return ans;
}

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