Submission #60826

#	Time	Username	Problem	Language	Result	Execution time	Memory
60826		hamzqq9	Friend (IOI14_friend)	C++14	46 / 100	61 ms	3268 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define sz(x) (x.size())
#define pb push_back
#define N 1005

int solve_naive(int n,int confidence[],int host[],int protocol[]) {

	int way[15][15]={0};

	for(int i=1;i<n;i++) {

		if(protocol[i]==1 || protocol[i]==2) {

			for(int j=0;j<n;j++) {

				if(way[host[i]][j]) {

					way[i][j]=way[j][i]=1;

				}

			}

		}

		if(protocol[i]==0 || protocol[i]==2) {

			way[host[i]][i]=way[i][host[i]]=1;

		}

	}

	int ans=0;

	for(int i=0;i<(1<<n);i++) {

		vector<int> took;
		int tot=0;

		for(int j=0;j<n;j++) {

			if(i&(1<<j)) {

				took.pb(j);
				tot+=confidence[j];

			}

		}

		bool flag=true;

		for(int j=0;j<sz(took);j++) {

			for(int k=0;k<j;k++) {

				if(way[took[j]][took[k]]) flag=false;

			}

		}

		if(flag==true) ans=max(ans,tot);

	}

	return ans;

}

vector<int> v[N];

int dp[2][N];

void dfs(int node,int confidence[]) {

	dp[1][node]=confidence[node];

	for(int i:v[node]) {

		dfs(i,confidence);

		dp[1][node]+=dp[0][i];

		dp[0][node]+=max(dp[0][i],dp[1][i]);

	}

}

int solve_tree(int n,int confidence[],int host[],int protocol[]) {

	for(int i=1;i<n;i++) v[host[i]].pb(i);

	dfs(0,confidence);

	return max(dp[0][0],dp[1][0]);

}

int solve_sum(int n,int confidence[],int host[],int protocol[]) {

	int sum=0;

	for(int i=0;i<n;i++) sum+=confidence[i];

	return sum;

}

int solve_max(int n,int confidence[],int host[],int protocol[]) {

	int maxx=0;

	for(int i=0;i<n;i++) maxx=max(maxx,confidence[i]);

	return maxx;

}

int findSample(int n,int confidence[],int host[],int protocol[]) {
	
	if(n<=10) return solve_naive(n,confidence,host,protocol);

	bool flag[3]={true,true,true};

	for(int i=1;i<n;i++) {

		for(int j=0;j<3;j++) {

			if(j==protocol[i]) flag[j]&=true;
			else flag[j]=false;

		}

	}

	if(flag[0]) return solve_tree(n,confidence,host,protocol);
	if(flag[1]) return solve_sum(n,confidence,host,protocol);
	if(flag[2]) return solve_max(n,confidence,host,protocol); 

	assert(0);

}

Compilation message (stderr)

friend.cpp: In function 'int solve_naive(int, int*, int*, int*)':
friend.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<sz(took);j++) {
                ^

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