oj.uz

답안 #924941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924941 2024-02-10T05:30:13 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 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] = max(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].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.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 -