Submission #643083

#TimeUsernameProblemLanguageResultExecution timeMemory
643083two_sidesCat in a tree (BOI17_catinatree)C++17
100 / 100
364 ms408900 KiB
#include <bits/stdc++.h> using namespace std; template <class X, class Y> bool cmax(X &a, const Y &b) { return a < b ? a = b, 1 : 0; } const int N = 2e5 + 5; const int D = 500; int dp[N][D], n, d, siz[N]; vector<int> adj[N]; void dfs1(int u) { dp[u][0] = 1; for (int v : adj[u]) { dfs1(v); for (int i = 0; i <= d; i++) cmax(dp[u][i], max(dp[v][max(i, d - i)] + dp[u][i], dp[v][i] + dp[u][max(i, d - i)])); } for (int i = d; i >= 0; i--) dp[u][i + 1] = dp[u][i]; for (int i = d; i >= 0; i--) cmax(dp[u][i], dp[u][i + 1]); } void dfs2(int u) { dp[u][0] = d - 1; dp[u][1] = 0; for (int v : adj[u]) { dfs2(v); siz[u] += siz[v] + 1; for (int i = siz[u] / d + 1; i >= 0; i--) for (int j = min(i, siz[v] / d + 1); j >= 0; j--) if (dp[u][i - j] + dp[v][j] + 1 >= d) cmax(dp[u][i], min(dp[u][i - j], dp[v][j] + 1)); } } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> d; for (int i = 1; i < n; i++) { int p; cin >> p; adj[p].push_back(i); } if (d + 1 < D) { dfs1(0); cout << dp[0][0]; } else { memset(dp, 0xc0, sizeof dp); dfs2(0); for (int i = D - 1; i >= 0; i--) if (dp[0][i] >= 0) { cout << i; break; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...