Submission #313553

#	Time	Username	Problem	Language	Result	Execution time	Memory
313553		tengiz05	Friend (IOI14_friend)	C++17	27 / 100	39 ms	1912 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int dp[1005][2];
int a[200005];
vector<int> edges[1005];
void dfs(int u, int p){
	dp[u][1] = a[u];
	for(auto v : edges[u]){
		if(v == p)continue;
		dfs(v, u);
		dp[u][0] += dp[v][1];
		dp[u][1] = max(dp[u][1], dp[v][0]);
	}
	dp[u][1] = max(dp[u][1], dp[u][0]);
}
int findSample(int n,int confidence[],int host[],int protocol[]){
	int ans=0;
	for(int i=0;i<n;i++)a[i] = confidence[i];
	if(n <= 15){
		int mask = 0;
		vector<int> friends[13];
		for(int i=1;i<n;i++){
			if(protocol[i] == 0){
				friends[i].pb(host[i]);
				friends[host[i]].pb(i);
			}else {
				for(auto x : friends[host[i]]){
					friends[i].pb(x);
					friends[x].pb(i);
				}
				if(protocol[i] == 2){
					friends[i].pb(host[i]);
					friends[host[i]].pb(i);
				}
			}
		}
		mask = 1;
		while(mask < (1<<n)){
			int cost = 0;
			vector<bool> used(n);
			for(int i=0;i<n;i++){
				if(!((1<<i)&mask))continue;
				bool ok = true;
				for(auto x : friends[i])if(used[x])ok=false;
				if(ok)cost += confidence[i], used[i] = true;
			}
			ans = max(cost, ans);
			mask++;
		}
	}else if(protocol[1] == 1){
		for(int i=0;i<n;i++)ans += confidence[i];
	}else if(protocol[1] == 2){
		for(int i=0;i<n;i++)ans = max(ans, confidence[i]);
	}else {
		for(int i=1;i<n;i++){
			edges[i].pb(host[i]);
			edges[host[i]].pb(i);
		}
		dfs(0, 0);
		ans = max(dp[0][0], dp[0][1]);
	}
	return ans;
}

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