Submission #1032242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032242		tolbi	Friend (IOI14_friend)	C++17	46 / 100	19 ms	4412 KiB

friend

#define tol(bi) (1LL<<((int)(bi)))
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	if (n<=1000){
		bool prot0=false;
		bool prot1=false;
		bool prot2=false;
		for (int i = 1; i < n; ++i)
		{
			if (protocol[i]==0) prot0=true;
			if (protocol[i]==1) prot1=true;
			if (protocol[i]==2) prot2=true;
		}
		vector<vector<int>> arr(n);
		for (int i = 1; i < n; i++){
			if (protocol[i]==0){
				arr[host[i]].push_back(i);
				arr[i].push_back(host[i]);
			}
			else if (protocol[i]==1){
				for (auto &fr : arr[host[i]]){
					arr[fr].push_back(i);
					arr[i].push_back(fr);
				}
			}
			else {
				for (auto &fr : arr[host[i]]){
					arr[fr].push_back(i);
					arr[i].push_back(fr);
				}
				arr[host[i]].push_back(i);
				arr[i].push_back(host[i]);
			}
		}
		if (n<=10){
			//subtask1
			int ret = 0;
			for (int i = 0; i < tol(n); i++){
				int cur = 0;
				for (int j = 0; j < n; j++){
					if (tol(j)&i){
						cur+=confidence[j];
						for (auto &nex : arr[j]){
							if (tol(nex)&i){
								cur=0;
								break;
							}
						}
						if (cur==0) break;
					}
				}
				ret=max(ret,cur);
			}
			return ret;
		}
		if (prot1 && !prot0 && !prot2){
			//subtask2
			int ret = 0;
			for (int i = 0; i < n; ++i)
			{
				ret+=confidence[i];
			}
			return ret;
		}
		if (prot2 && !prot0 && !prot1){
			//subtask3
			int ret = 0;
			for (int i = 0; i < n; ++i){
				ret=max(ret,confidence[i]);
			}
			return ret;
		}
		if (prot0 && !prot1 && !prot2){
			//subtask4
			vector<array<int,2>> dp(n,{-1,-1});
			function<int(int,int,int)> f = [&](int node, int lnode, int flag)->int{
				if (dp[node][flag]!=-1) return dp[node][flag];
				dp[node][flag]=0;
				for (auto &nex : arr[node]){
					if (nex==lnode) continue;
					dp[node][flag]+=f(nex,node,0);
				}
				if (flag==1){
					return dp[node][flag];
				}
				int nn = confidence[node];
				for (auto &nex : arr[node]){
					if (nex==lnode) continue;
					nn+=f(nex,node,1);
				}
				return dp[node][flag]=max(dp[node][flag],nn);
			};
			return f(0,-1,0);
		}
		if (prot0 && prot1 && !prot2){
			//subtask5
			vector<array<int,2>> dp(n,{0,0});
			dp[0][1]=confidence[0];
			for (int i = 1; i < n; i++){
				if (protocol[i]==0){
					dp[i][1]=dp[host[i]][0]+confidence[i];
				}
				else {
					dp[i][1]=dp[host[i]][1]+confidence[i];
				}
				dp[i][0]=max(dp[host[i]][0],dp[host[i]][1]);
			}
			return max(dp[n-1][0],dp[n-1][1]);
		}
	}
	return 23;
}

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