Submission #719070

#	Time	Username	Problem	Language	Result	Execution time	Memory
719070		mseebacher	Friend (IOI14_friend)	C++17	11 / 100	1075 ms	65536 KiB

friend

#include "friend.h"
#include <bits/stdc++.h> 

using namespace std;

vector<set<int>> friends;

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	friends.assign(n,{});
	for(int i = 1;i<n;i++){
		if(protocol[i] == 0){
			friends[i].insert(host[i]);
			friends[host[i]].insert(i);
		}else{
			set<int>::iterator it = friends[host[i]].begin();
			for(;it != friends[host[i]].end();it++){
				int f = *it;
				friends[f].insert(i);
				friends[i].insert(f);
			}
			if(protocol[i] == 2){
				friends[i].insert(host[i]);
				friends[host[i]].insert(i);
			}
		}	
		 
	}
	
	long long ans = 0;
	for(int mask = 0;mask<(1<<n);mask++){
		vector<int> x;
		long long sum = 0;
		for(int i = 0;i<n;i++){
			if(mask & (1 << i)){
				x.push_back(i);
				sum += confidence[i];
			}
		}
		bool b = 1;
		for(int i = 0;i<(int)x.size();i++){
			for(int j = i+1;j<(int)x.size();j++){
				if(friends[x[i]].find(x[j]) != friends[x[i]].end()){
					b = 0;
					break;
				}
			}
			if(!b) break;
		}
		if(b){
			ans = max(ans,sum);
		}
	}
	return ans;
}

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