Submission #865186

#TimeUsernameProblemLanguageResultExecution timeMemory
865186maks007Cat in a tree (BOI17_catinatree)C++14
0 / 100
3 ms18012 KiB
// Bismi ALlah #include "bits/stdc++.h" using namespace std; #define int long long int dp[1501][1501]; signed main () { int n, d; cin >> n >> d; vector <int> g[n]; memset(dp, 0, sizeof(dp)); function <void(int,int)> dfs=[&](int v, int p) { vector <int> child; for(auto u : g[v]) { if(u == p) continue; dfs(u, v); child.push_back(u); } for(int Dist = 1500; Dist >= 0; Dist --) { if(Dist == 0) { int temp = 1; for(auto other : child) { temp += dp[other][d-1]; } dp[v][Dist] = max(temp, dp[v][Dist]); } int sum = 0; for(auto other : child) { sum +=/* max(dp[other][max(0LL, Dist-1)],*/ dp[other][max(0LL, Dist-1)]/*)*/; } dp[v][Dist] = max(sum, dp[v][Dist]); } }; for(int i = 1; i < n; i ++) { int p; cin >> p; g[i].push_back(p); g[p].push_back(i); } dfs(0, -1); int ans = -1e9; for(int i = 0; i <= 1500; i ++) ans = max(ans, dp[0][i]); /* for(int i = 0; i < n; i ++) { for(int j = 0; j < d; j ++) { cout << i << " " << j << " " << dp[i][j] << "\n"; } }*/ cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...