Submission #924920

#	Time	Username	Problem	Language	Result	Execution time	Memory
924920		Jawad_Akbar_JJ	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	1 ms	600 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);

		// if (u == 12){
		// 	cout<<"[1] : ";
		// 	print(Mx[1][12]);
		// 	cout<<"[0] : ";
		// 	print(Mx[0][12]);
		// 	cout<<"[1][i] "<<i<<" : ";
		// 	print(Mx[1][i]);
		// }

		for (int j=n;j>=1;j--){
			if (Mx[1][i][j-1] != 0)
				Mx[0][u][j] = max(Mx[1][u][j],Mx[1][i][j-1] + Mx[1][u][d - j]);
		}
		copy(Mx[0][u],Mx[1][u]);
		clear(Mx[0][u]);
	}

	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;
	// }
}

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