Submission #48997

#	Time	Username	Problem	Language	Result	Execution time	Memory
48997		Namnamseo	Friend (IOI14_friend)	C++17	35 / 100	3 ms	1592 KiB

friend

#include "friend.h"

// Find out best sample

int sum[100001][2];

int max(int a,int b){ return a>b?a:b; }
int min(int a,int b){ return a<b?a:b; }

bool edge[11][11];

int naive(int n,int cf[],int hst[],int pt[]){
	for(int i=1; i<n; ++i){
		int h=hst[i];
		if(pt[i] == 0){
			edge[h][i]=edge[i][h]=true;
		} else {
			for(int j=0; j<n; ++j) if(edge[h][j]) edge[j][i]=edge[i][j]=true;
			if(pt[i] == 2){
				edge[h][i]=edge[i][h]=true;
			}
		}
	}
	int msk=(1<<n);
	int ans=0;
	for(int i=0; i<msk; ++i){
		int s[11], t=0;
		int cur=0;
		for(int j=0; j<n; ++j) if(1&(i>>j)) s[t++]=j, cur+=cf[j];
		bool wa=0;
		for(int a=0; a<t; ++a){
			for(int b=a+1; b<t; ++b){
				if(edge[s[a]][s[b]]){
					wa=1; break;
				}
			}
			if(wa) break;
		}
		if(!wa) ans=max(ans, cur);
	}
	return ans;
}
#include <cstdio>
int findSample(int n,int confidence[],int host[],int protocol[]){
	if(n <= 10){
//		return naive(n,confidence,host, protocol);
	}
	for(int i=0; i<n; ++i) sum[i][1]=confidence[i], sum[i][0]=0;
	int allprot=0;
	for(int i=n-1; 0<i; --i){
		int h=host[i];
		int p=protocol[i];
		if(p==2) ++allprot;
		if(p == 0){
			sum[h][0] += max(sum[i][0], sum[i][1]);
			sum[h][1] += sum[i][0];
		} else if(p == 1){
			sum[h][0] += sum[i][0];
			sum[h][1] += max(sum[i][0], sum[i][1]);
		} else if(p == 2){
			sum[h][1] += max(0, -confidence[h] + max(sum[i][0], sum[i][1]));
			sum[h][0] += sum[i][0];
		}
		//printf("Host(%d)| %d %d\n", h, sum[h][1], sum[h][0]);
	}
	if(allprot == n-1){
		int ans=0;
		for(int i=0; i<n; ++i) ans=max(ans, confidence[i]);
		return ans;
	}
	return max(sum[0][0], sum[0][1]);
}

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