Submission #1015421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015421		parsadox2	Friend (IOI14_friend)	C++17	11 / 100	1100 ms	2336 KiB

friend

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

using namespace std;

const int N = 1e5 + 10;
int n , ar[N] , adj[N] , dp[(1 << 11)];

int findSample(int nn,int confidence[],int host[],int protocol[]){
	n = nn;
	for(int i = 0 ; i < n ; i++)
		ar[i] = confidence[i];
	for(int i = 1 ; i < n ; i++)
	{
		if(protocol[i] != 0)
		{
			for(int j = 0 ; j < n ; j++)  if((adj[host[i]] >> j) & 1)
			{
				adj[i] |= (1 << j);
				adj[j] |= (1 << i);
			}
		}
		if(protocol[i] != 1)
		{
			adj[i] |= (1 << host[i]);
			adj[host[i]] |= (1 << i);
		}
	}
	for(int mask = (1 << n) - 1 ; mask >= 0 ; mask--)
	{
		for(int i = 0 ; i < n ; i++)
		{
			int tmp = (adj[i] | (1 << i));
			if((mask & tmp) == 0)
				dp[mask] = max(dp[mask] , dp[(mask | (1 << i))] + ar[i]);
		}
	}
	return dp[0];
}

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