Submission #924921

#	Time	Username	Problem	Language	Result	Execution time	Memory
924921		Jawad_Akbar_JJ	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	0 ms	344 KiB

catinatree

#include <iostream>
#include <vector>

using namespace std;
const int N = 1500 + 10;
vector<int> ch[N];
int Mx[2][N][N];
int n,d;

void copy(int a[],int b[]){// copy a to b
	for (int i=n;i>=1;i--)
		b[i] = max(b[i+1], a[i]);
}
void clear(int a[]){
	for (int i=n;i>=0;i--)
		a[i] = 0;
}

void print(int a[]){
	for (int i=0;i<=n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}

void dfs(int u){
	// cout<<u<<endl;
	for (int i : ch[u])
		dfs(i);
	for (int i : ch[u])
		for (int v : ch[u])
			if (i != v)
				for (int j=1;j<=n;j++)
					Mx[1][u][j] = max(Mx[1][u][j],Mx[1][i][j-1] + Mx[1][v][d - j]);
	for (int i=n;i>=1;i--)
		Mx[1][u][i] = max(Mx[1][u][i],Mx[1][u][i+1]);
	Mx[1][u][0] = Mx[1][u][d] + 1;
}

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

	for (int i=2;i<=n;i++){
		int p;
		cin>>p;
		ch[p + 1].push_back(i);
		// cout<<p<<" "<<i<<endl;
	}

	if (d > n){
		cout<<1<<endl;
		return 0;
	}

	// cout<<Mx[1][3][0]<<" "<<Mx[1][2][1]<<endl;

	dfs(1);

	cout<<max(Mx[1][1][0],Mx[1][1][1])<<endl;

	// for (int i=1;i<=n;i++){
	// 	cout<<i<<" : ";
	// 	for (int j=0;j<=n;j++)
	// 		cout<<Mx[1][i][j]<<" ";
	// 	cout<<endl;
	// }
}
// 24 3
// 1 1 1 2 2 4 4 4 5 6 6 8 8 9 12 12 12 12 13 13 14 15 15

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