Submission #1048188

#TimeUsernameProblemLanguageResultExecution timeMemory
1048188duckindogCat in a tree (BOI17_catinatree)C++17
51 / 100
6 ms13144 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2'000 + 10; int n, d; vector<int> ad[N]; int f[N][N], maxV[N], maxU[N]; void dfs(int u, int p = -1) { f[u][0] = 1; for (const auto& v : ad[u]) { dfs(v, u); for (int i = d; i >= 0; --i) { maxU[i] = max(f[u][i], maxU[i + 1]); maxV[i] = max(f[v][i], maxV[i + 1]); } for (int i = 0; i <= d; ++i) { auto& ret = f[u][i]; ret = max(ret, f[u][i] + maxV[max(i, d - i - 1)]); if (i) ret = max(ret, f[v][i - 1] + maxU[max(i, d - i)]); } } } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> d; for (int v = 1; v < n; ++v) { int u; cin >> u; ad[u].push_back(v); } dfs(0); cout << *max_element(f[0], f[0] + d + 1) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...