Submission #986765

#	Time	Username	Problem	Language	Result	Execution time	Memory
986765		Jawad_Akbar_JJ	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	20 ms	15448 KiB

catinatree

#include <iostream>
#include <vector>

using namespace std;
const int N = 2500;
vector<int> nei[N];
int dp[N][N], D, n, temp[N];

void dfs(int u){
	dp[u][0] = 1;
	for (int i : nei[u]){
		dfs(i);

		for (int i=0;i<=n;i++)
			temp[i] = 0;

		dp[i][D-1] = max(dp[i][D-1],dp[i][D]);
		int mx = 0;
		for (int d = 1;d<=D;d++){
			mx = max(mx,dp[u][D - d]);
			int k = min(d,D - d);
			temp[k] = max(temp[k],dp[i][d-1] + mx);
		}
		mx = 0;
		for (int d = 1;d<=D;d++)
			temp[d] = max(temp[d],dp[i][d-1]);
		
		for (int d=n;d + d >= D;d--){
			mx = max(mx,dp[u][d]);
			temp[d] = max(temp[d],mx + dp[i][d-1]);
		}

		for (int j=n;j>=0;j--){
			dp[u][j] = max(dp[u][j],temp[j]);
			dp[u][j] = max(dp[u][j],dp[u][j+1]);
		}
	}
}

int main(){
	cin>>n>>D;

	for (int i=2;i<=n;i++){
		int p;
		cin>>p;
		nei[p + 1].push_back(i);
	}

	dfs(1);

	int ans = 0;

	for (int i=0;i<=n;i++)
		ans = max(ans,dp[1][i]);
	cout<<ans<<'\n';
}


// next

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