Submission #313541

#	Time	Username	Problem	Language	Result	Execution time	Memory
313541		tengiz05	Friend (IOI14_friend)	C++17	27 / 100	37 ms	1528 KiB

friend

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

int findSample(int n,int confidence[],int host[],int protocol[]){
	int ans=0;
	if(n <= 12){
		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 {
		for(int i=0;i<n;i++)ans = max(ans, confidence[i]);
	}
	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