Submission #143241

#	Time	Username	Problem	Language	Result	Execution time	Memory
143241		davitmarg	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	757 ms	410988 KiB

catinatree

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n,d,dp[200005][502],upd[502],sz[200005],ans=1,D;
vector<int> g[200005];
void dfs(int v)
{
	sz[v]=1;
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		dfs(to);
	}

	dp[v][0]=1;
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];

		for(int k1=0;k1<=d && k1<=sz[v];k1++)
			upd[k1]=dp[v][k1];
		for(int k1=0;k1<=d && k1<=sz[v];k1++)
			for(int k2=0;k2<=d && k2<=sz[to];k2++)
				if(k1+k2+1>=d)
					dp[v][min(k2+1,k1)]=max(dp[v][min(k2+1,k1)],dp[to][k2]+upd[k1]);

		for(int k2=0;k2<=d && k2<=sz[to];k2++)
			dp[v][k2+1]=max(dp[to][k2],dp[v][k2+1]);

		sz[v]+=sz[to];
		for(int k=d;k>=0;k--)
			dp[v][k]=max(dp[v][k],dp[v][k+1]);
	}


	for(int k=0;k<=d;k++)
		ans=max(ans,dp[v][k]);
}


void dfs2(int v)
{
	sz[v]=1;
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		dfs2(to);
	}

	dp[v][1]=0;
	dp[v][0]=mod;

	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		for(int k1=min(D,sz[v]);k1>=0;k1--)
			for(int k2=0;k2<=D && k2<=sz[to];k2++)
				if(dp[v][k1]+dp[to][k2]+1>=d)
					dp[v][k1+k2]=max(dp[v][k1+k2],min(dp[v][k1],dp[to][k2]+1));
		sz[v]+=sz[to];
	}
	
	// cout<<"!"<<v<<endl;
	// for(int k1=0;k1<=D && k1<=sz[v];k1++)
	// 	cout<<k1<<" = "<<dp[v][k1]<<endl;
	// cout<<endl;

	for(int k1=1;k1<=D && k1<=sz[v];k1++)
		if(dp[v][k1]>=0)
			ans=max(ans,k1);

}

int main()
{
	cin>>n>>d;
	for(int i=1;i<n;i++)
	{
		int p;
		scanf("%d",&p);
		g[p].PB(i);
	}
	D=(n-1)/d+1;
	D++;
	if(D<=d)
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<=D;j++)
				dp[i][j]=-mod;
		dfs2(0);
	}
	else
		dfs(0);

	cout<<ans<<endl;
	return 0;
}
 
/*

2 3
0 

4 3
0
0
0

*/

Compilation message (stderr)

catinatree.cpp: In function 'void dfs(int)':
catinatree.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
catinatree.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
catinatree.cpp: In function 'void dfs2(int)':
catinatree.cpp:66:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
catinatree.cpp:75:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);
   ~~~~~^~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49