Submission #404208

#	Time	Username	Problem	Language	Result	Execution time	Memory
404208		wmrmr	Friend (IOI14_friend)	C++17	46 / 100	32 ms	4584 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5;

bool adj[10][10];
int dp[MAX][2];
vector<int> g[MAX];

void pt4_DFS(int v, int pai)
{
	for( int i=0;i<g[v].size();i++ )
	{
		int prox = g[v][i];
		if(prox == pai) continue;
		pt4_DFS(prox,v);
		dp[v][0] += max( dp[prox][0] , dp[prox][1]);
		dp[v][1] += dp[prox][0];	
	}
}

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	int ans = 0;
	bool pt2 = 1, pt3 = 1, pt4 = 1;
	for(int i=1;i<n;i++)
	{
		if(protocol[i] != 0) pt4 = 0;
		if(protocol[i] != 1) pt2 = 0;
		if(protocol[i] != 2) pt3 = 0;
	}
	for(int i=0;i<n;i++) dp[i][1] = confidence[i];
	if(n <= 10)
	{
		ans = 0;
		for(int i=1;i<n;i++)
		{
			int p = host[i];
			if(protocol[i] != 1) adj[i][p] = adj[p][i] = 1;
			if(protocol[i] != 0)
				for(int j=0;j<i;j++)
					adj[i][j] = adj[j][i] = adj[j][i] || adj[p][j];
		}
		int dbg = 0;
		for(int cur = 0 ; cur < (1<<n) ; cur++)
		{
			bool valid = 1;
			for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
			{
				if( (cur&(1<<i)) && (cur&(1<<j)) )
					if(adj[i][j]) valid = 0;
			}
			int temp = 0;
			for(int i=0;i<n;i++)
				if(cur&(1<<i)) temp += confidence[i];
			if(valid) ans = max(ans,temp), dbg = cur;
		}
		return ans;
	}
	if(pt2)
	{
		for(int i=0;i<n;i++) ans += confidence[i];
		return ans;
	}
	if(pt3)
	{
		for(int i=0;i<n;i++) ans = max(ans,confidence[i]);
		return ans;
	}
	if(n <= 1e3)
	{
		for(int i=1;i<n;i++)
		{
			int p = host[i];
			if(protocol[i] != 1) g[i].push_back(p), g[p].push_back(i);
			if(protocol[i] != 0)
			{
				for(int j=0;j<g[p].size();j++)
				{
					int prox = g[p][j];
					g[prox].push_back(i); g[i].push_back(prox);
				}
			}
		}
	}
	if(pt4)
	{
		pt4_DFS(0,0);
		return max( dp[0][0] , dp[0][1] );
	}
		
	return 0;
}

Compilation message (stderr)

friend.cpp: In function 'void pt4_DFS(int, int)':
friend.cpp:12:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for( int i=0;i<g[v].size();i++ )
      |               ~^~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:44:7: warning: variable 'dbg' set but not used [-Wunused-but-set-variable]
   44 |   int dbg = 0;
      |       ^~~
friend.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int j=0;j<g[p].size();j++)
      |                 ~^~~~~~~~~~~~

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