Submission #589412

#	Time	Username	Problem	Language	Result	Execution time	Memory
589412		yutabi	Friend (IOI14_friend)	C++14	100 / 100	26 ms	2668 KiB

friend

#include "friend.h"


#include <bits/stdc++.h>
using namespace std;


#define pb push_back



bool graph[1003][1003];

int subtask1(int n,int confidence[],int host[],int protocol[])
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			graph[i][j]=0;
		}
	}

	for(int i=1;i<n;i++)
	{
		if(protocol[i]!=0)
		{
			for(int j=0;j<n;j++)
			{
				if(graph[host[i]][j])
				{
					graph[j][i]=graph[i][j]=1;
				}
			}
		}

		if(protocol[i]!=1)
		{
			graph[host[i]][i]=graph[i][host[i]]=1;
		}
	}

	int ans=0;

	for(int i=0;i<1<<n;i++)
	{
		vector <int> nums;

		int curr=0;

		for(int j=0,k=i;k;j++,k/=2)
		{
			if(k%2)
			{
				nums.pb(j);

				curr+=confidence[j];
			}
		}

		bool flag=0;

		for(int j=0;j<nums.size();j++)
		{
			for(int k=0;k<nums.size();k++)
			{
				if(graph[nums[j]][nums[k]])
				{
					flag=1;
				}
			}
		}

		if(!flag)
		{
			ans=max(ans,curr);
		}
	}

	return ans;
}

int subtask2(int n,int confidence[],int host[],int protocol[])
{
	int ans=0;

	for(int i=0;i<n;i++)
	{
		ans+=confidence[i];
	}

	return ans;
}

int subtask3(int n,int confidence[],int host[],int protocol[])
{
	int ans=0;

	for(int i=0;i<n;i++)
	{
		ans=max(ans,confidence[i]);
	}

	return ans;
}



int DP[1003][2];

int* con;

void DFS(int node,int parent)
{
	int ans1=0;
	int ans2=0;

	for(int i=0;i<1003;i++)
	{
		if(graph[node][i] && i!=parent)
		{
			DFS(i,node);

			ans1+=DP[i][0];
			ans2+=DP[i][1];
		}
	}

	ans1+=con[node];

	ans1=max(ans1,ans2);

	DP[node][0]=ans2;
	DP[node][1]=ans1;
}

int subtask4(int n,int confidence[],int host[],int protocol[])
{
	con=confidence;

	for(int i=0;i<1003;i++)
	{
		for(int j=0;j<1003;j++)
		{
			graph[i][j]=0;
		}
	}

	for(int i=1;i<n;i++)
	{
		if(protocol[i]!=0)
		{
			for(int j=0;j<n;j++)
			{
				if(graph[host[i]][j])
				{
					graph[j][i]=graph[i][j]=1;
				}
			}
		}

		if(protocol[i]!=1)
		{
			graph[host[i]][i]=graph[i][host[i]]=1;
		}
	}

	DFS(0,-1);

	return DP[0][1];
}

int findSample(int n,int confidence[],int host[],int protocol[])
{
	/*if(n<=10)
	{
		return subtask1(n,confidence,host,protocol);
	}

	if(protocol[1]==1)
	{
		return subtask2(n,confidence,host,protocol);
	}

	if(protocol[1]==2)
	{
		return subtask3(n,confidence,host,protocol);
	}

	if(protocol[1]==0)
	{
		return subtask4(n,confidence,host,protocol);
	}


	bool oopsie=0;

	assert(oopsie);*/



	int ans=0;

	for(int i=n-1;i>=0;i--)
	{
		if(protocol[i]==0)
		{
			ans+=confidence[i];

			confidence[host[i]]-=confidence[i];

			confidence[host[i]]=max(confidence[host[i]],0);
		}

		if(protocol[i]==1)
		{
			confidence[host[i]]+=confidence[i];
		}

		if(protocol[i]==2)
		{
			confidence[host[i]]=max(confidence[host[i]],confidence[i]);
		}
	}

	ans+=confidence[0];

	return ans;
}

Compilation message (stderr)

friend.cpp: In function 'int subtask1(int, int*, int*, int*)':
friend.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int j=0;j<nums.size();j++)
      |               ~^~~~~~~~~~~~
friend.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for(int k=0;k<nums.size();k++)
      |                ~^~~~~~~~~~~~

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