Submission #217972

#	Time	Username	Problem	Language	Result	Execution time	Memory
217972		Pajaraja	Friend (IOI14_friend)	C++17	100 / 100	96 ms	13304 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
#define MAXN 100007
using namespace std;
vector<int> g[MAXN],w[MAXN];
int p[MAXN],c[MAXN],dp[2][MAXN],y[MAXN],t[MAXN];
void dfs(int s)
{
	for(int i=0;i<g[s].size();i++) dfs(g[s][i]);
	for(int i=0;i<g[s].size();i++)
	{
		if(w[s][i]==0 || w[s][i]==2) dp[1][s]+=y[g[s][i]];
		if(w[s][i]==1) dp[1][s]+=max(dp[0][g[s][i]],dp[1][g[s][i]]);
		if(w[s][i]==0) y[s]+=max(dp[0][g[s][i]],dp[1][g[s][i]]);
		if(w[s][i]==1 || w[s][i]==2) y[s]+=y[g[s][i]];
	}
	dp[1][s]+=c[s];
	if(g[s].size()==0) return;
	vector<int> kr;
	for(int i=0;i<g[s].size();i++) kr.push_back(0);
	for(int i=(int)kr.size()-1;i>=0;i--) 
	{
		if(i!=(int)kr.size()-1) kr[i]=kr[i+1];
		if(w[s][i]==0) kr[i]+=max(dp[0][g[s][i]],dp[1][g[s][i]]); 
		if(w[s][i]!=0) kr[i]+=y[g[s][i]]; 
	}
	int sum=0,mx=kr[0];
	for(int i=0;i<g[s].size();i++)
	{
		if(w[s][i]==0) for(int j=0;j<g[g[s][i]].size();j++)
		{
			if(t[g[g[s][i]][j]]==0) sum+=max(dp[0][g[g[s][i]][j]],dp[1][g[g[s][i]][j]]);
			else sum+=y[g[g[s][i]][j]];
		}
		if(w[s][i]!=0) 
		{
			int t=sum+max(dp[1][g[s][i]],dp[0][g[s][i]]);
			if(i!=(int)kr.size()-1) t+=kr[i+1];
			mx=max(mx,t);
		}
		if(w[s][i]==1) sum+=max(dp[1][g[s][i]],dp[0][g[s][i]]);
		if(w[s][i]==2) sum+=y[g[s][i]];
	}
	dp[0][s]=mx;
}
int findSample(int n,int confidence[],int host[],int protocol[])
{
	for(int i=0;i<n;i++) c[i]=confidence[i]; 
	for(int i=1;i<n;i++) {p[i]=host[i]; g[p[i]].push_back(i); w[p[i]].push_back(protocol[i]); t[i]=protocol[i];}
	dfs(0);
	return max(dp[0][0],dp[1][0]);
}

Compilation message (stderr)

friend.cpp: In function 'void dfs(int)':
friend.cpp:9:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) dfs(g[s][i]);
              ~^~~~~~~~~~~~
friend.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++)
              ~^~~~~~~~~~~~
friend.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) kr.push_back(0);
              ~^~~~~~~~~~~~
friend.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++)
              ~^~~~~~~~~~~~
friend.cpp:30:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(w[s][i]==0) for(int j=0;j<g[g[s][i]].size();j++)
                              ~^~~~~~~~~~~~~~~~~~

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