Submission #292540

#	Time	Username	Problem	Language	Result	Execution time	Memory
292540		TMJN	Friend (IOI14_friend)	C++17	30 / 100	37 ms	2680 KiB

friend

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

int solve_1(int n,int confidence[],int host[],int protocol[]){
	vector<int>v[10];
	for(int i=1;i<n;i++){
		if(protocol[i]==0){
			v[i].push_back(host[i]);
			v[host[i]].push_back(i);
		}
		if(protocol[i]==1){
			for(int j:v[host[i]]){
				v[j].push_back(i);
				v[i].push_back(j);
			}
		}
		if(protocol[i]==2){
			for(int j:v[host[i]]){
				v[j].push_back(i);
				v[i].push_back(j);
			}
			v[i].push_back(host[i]);
			v[host[i]].push_back(i);
		}
	}
	int res=0;
	for(int i=0;i<(1<<n);i++){
		bool b[10];
		for(int j=0;j<n;j++){
			b[j]=(i>>j)&1;
		}
		bool f=true;
		int c=0;
		for(int j=0;j<n;j++){
			if(!b[j])continue;
			c+=confidence[j];
			for(int k:v[j]){
				if(b[k])f=false;
			}
		}
		if(f&&res<c)res=c;
	}
	return res;
}

int solve_2(int n,int confidence[],int host[],int protocol[]){
	int res=0;
	for(int i=0;i<n;i++){
		res+=confidence[i];
	}
	return res;
}

int solve_3(int n,int confidence[],int host[],int protocol[]){
	int res=0;
	for(int i=0;i<n;i++){
		if(res<confidence[i])res=confidence[i];
	}
	return res;
}

vector<int>v_4[1000];
int C_4[1000][2];

void dfs_4(int x,int from){
	for(int i:v_4[x]){
		if(i==from)continue;
		dfs_4(i,x);
		C_4[x][0]+=max(C_4[i][0],C_4[i][1]);
		C_4[x][1]+=C_4[i][0];
	}
}

int solve_4(int n,int confidence[],int host[],int protocol[]){
	for(int i=1;i<n;i++){
		v_4[i].push_back(host[i]);
		v_4[host[i]].push_back(i);
	}
	for(int i=0;i<n;i++){
		C_4[i][1]=confidence[i];
	}
	dfs_4(0,0);
	return max(C_4[0][0],C_4[0][1]);
}

int solve_5(int n,int confidence[],int host[],int protocol[]){
	return -1;
}


int findSample(int n,int confidence[],int host[],int protocol[]){
	if(n<=10){
		return solve_1(n,confidence,host,protocol);
	}
	bool used[3],f;
	for(int i=0;i<3;i++)used[i]=false;
	f=true;
	for(int i=0;i<n;i++){
		if(confidence[i]!=1)f=false;
		used[protocol[i]]=true;
	}
	if(!used[0]&&used[1]&&!used[2]){
		return solve_2(n,confidence,host,protocol);
	}
	if(!used[0]&&!used[1]&&used[2]){
		return solve_3(n,confidence,host,protocol);
	}
	if(used[0]&&!used[1]&&!used[2]){
		return solve_4(n,confidence,host,protocol);
	}
	if(f&&!used[2]){
		return solve_5(n,confidence,host,protocol);
	}
	return -1;
}

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