Submission #430404

#	Time	Username	Problem	Language	Result	Execution time	Memory
430404		frodakcin	Friend (IOI14_friend)	C++17	11 / 100	29 ms	2548 KiB

friend

#include "friend.h"
#include <vector>

template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}

// Find out best sample
const int MN = 10;
std::vector<int> a[MN];
void adde(int u, int v) {a[u].push_back(v), a[v].push_back(u);}

int findSample(int n,int confidence[],int host[],int protocol[])
{
	if(n>10) return -1;

	for(int i=1;i<n;++i)
	{
		if(protocol[i] == 1 || protocol[i] == 2)
			for(int x:a[host[i]])
				adde(x, i);
		if(protocol[i] == 0 || protocol[i] == 2)
			adde(host[i], i);
	}

	int ans=0;
	for(int i=1;i<(1<<n);++i)
	{
		bool ok=1;
		for(int j=0;ok&&j<n;++j)
			if(i>>j&1)
				for(int k:a[j])
					if(i>>k&1)
					{
						ok=0;
						break;
					}

		int v=0;
		for(int j=0;j<n;++j)
			if(i>>j&1) v += confidence[j];
		if(ok)
			ckmax(ans, v);
	}
	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