Submission #986364

#	Time	Username	Problem	Language	Result	Execution time	Memory
986364		Pyqe	Friend (IOI14_friend)	C++17	100 / 100	60 ms	15616 KiB

friend

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const int inf=1e9;
int n,nn,a[200069],pr[200069],kya[200069],kd[200069],sr[200069],pst[200069],dp[200069][2];
bitset<200069> lf;
vector<int> al[200069];

void dfs(int x)
{
	int i,sz=al[x].size(),l,mx=-inf;
	
	dp[x][0]=0;
	dp[x][1]=0;
	if(!kd[x])
	{
		dp[x][1]=a[x];
	}
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		dfs(l);
		if(!kya[l])
		{
			dp[x][0]+=dp[l][1];
			dp[x][1]+=dp[l][0];
		}
		else if(kya[l]==1)
		{
			dp[x][0]+=dp[l][0];
			dp[x][1]+=dp[l][1];
		}
		else
		{
			dp[x][0]+=dp[l][0];
			dp[x][1]+=dp[l][0];
			mx=max(mx,dp[l][1]-dp[l][0]);
		}
	}
	if(kd[x]==2)
	{
		dp[x][1]+=mx;
	}
	dp[x][1]=max(dp[x][1],dp[x][0]);
}

int findSample(int on,int oa[],int opr[],int okya[])
{
	int i;
	
	n=on;
	nn=n;
	for(i=1;i<=n;i++)
	{
		a[i]=oa[i-1];
		pr[i]=opr[i-1]+1;
		kya[i]=okya[i-1];
		sr[i]=i;
		pst[i]=i;
		lf[i]=1;
		if(i==1)
		{
			pr[i]=0;
		}
		else
		{
			pr[i]=pst[pr[i]];
			if(!kya[i]);
			else
			{
				if(lf[pr[i]]&&kya[pr[i]]==kya[i]&&pr[pr[i]]&&kd[pr[pr[i]]]==kya[i])
				{
					pr[i]=pr[pr[i]];
				}
				else
				{
					nn++;
					a[nn]=a[pr[i]];
					pr[nn]=pr[i];
					kya[nn]=kya[i];
					lf[nn]=1;
					sr[nn]=sr[pr[i]];
					pst[sr[pr[i]]]=nn;
					a[pr[i]]=0;
					kd[pr[i]]=kya[i];
					sr[pr[i]]=0;
				}
			}
		}
		lf[pr[i]]=0;
	}
	for(i=2;i<=nn;i++)
	{
		al[pr[i]].push_back(i);
	}
	dfs(1);
	return dp[1][1];
}

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