Submission #143018

#	Time	Username	Problem	Language	Result	Execution time	Memory
143018		davitmarg	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	59 ms	28664 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[2000][2000],upd[2000][2000],sz[200005],ans=1;
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++)
			for(int k2=0;k2<=d && k2<=sz[to];k2++)
				if(k1+k2+1>=d)
					upd[v][min(k2+1,k1)]=max(upd[v][min(k2+1,k1)],dp[to][k2]+dp[v][k1]);

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

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

	// cout<<"! "<<v<<endl;
	// for(int k=0;k<=d && k<=sz[v];k++)
	// 	cout<<k<<" = "<<dp[v][k]<<"\n";

	for(int k=0;k<=d;k++)
		ans=max(ans,dp[v][k]);
}
int main()
{
	cin>>n>>d;
	for(int i=1;i<n;i++)
	{
		int p;
		scanf("%d",&p);
		g[p].PB(i);
	}
	dfs(0);
	cout<<ans<<endl;
	return 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 'int main()':
catinatree.cpp:71: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: 0 / 49