Submission #59262

#	Time	Username	Problem	Language	Result	Execution time	Memory
59262		TadijaSebez	Friend (IOI14_friend)	C++11	100 / 100	129 ms	11972 KiB

friend

#include <stdio.h>
#include <vector>
using namespace std;
#define mp make_pair
#define pb push_back
const int N=100050;
int p[N],q[N],c[N];
vector<pair<int,int> > E[N];
void AddEdge(int u, int v, int w){ E[u].pb(mp(v,w));}
int max(int a, int b){ return a>b?a:b;}
int max(int a, int b, int c){ return max(a,max(b,c));}
void DFS(int u)
{
	p[u]=c[u];q[u]=0;
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i].first;
		int w=E[u][i].second;
		DFS(v);
		if(w==0)
		{
			q[u]+=max(q[v],p[v]);
			p[u]+=q[v];
		}
		if(w==1)
		{
			p[u]=max(p[u]+p[v],p[u]+q[v],p[v]+q[u]);
			q[u]+=q[v];
		}
		if(w==2)
		{
			p[u]=max(p[u]+q[v],p[v]+q[u]);
			q[u]+=q[v];
		}
		//printf("%i %i %i:%i %i\n",u-1,v-1,w,p[u],q[u]);
	}
}
int findSample(int n, int co[], int par[], int ty[])
{
	int i;
	for(i=n-1;i;i--) AddEdge(par[i]+1,i+1,ty[i]);
	//for(i=1;i<n;i++) if(ty[i]==2) AddEdge(par[i]+1,i+1,ty[i]);
	//for(i=1;i<n;i++) if(ty[i]==1) AddEdge(par[i]+1,i+1,ty[i]);
	//for(i=1;i<n;i++) if(ty[i]==0) AddEdge(par[i]+1,i+1,ty[i]);
	for(i=1;i<=n;i++) c[i]=co[i-1];
	DFS(1);
	return max(p[1],q[1]);
}

Compilation message (stderr)

friend.cpp: In function 'void DFS(int)':
friend.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++)
              ~^~~~~~~~~~~~

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