제출 #924941

#제출 시각아이디문제언어결과실행 시간메모리
924941Jawad_Akbar_JJCat in a tree (BOI17_catinatree)C++17
0 / 100
0 ms348 KiB
#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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...