oj.uz

답안 #924912

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924912 2024-02-10T04:11:30 Z Jawad_Akbar_JJ Cat in a tree (BOI17_catinatree) C++17
0 / 100
 0 ms 348 KB 
#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 dfs(int u){
	// cout<<u<<endl;
	for (int i : ch[u]){
		dfs(i);
		for (int j=n;j>=1;j--)
			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);
	}

	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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -