Submission #559267

#TimeUsernameProblemLanguageResultExecution timeMemory
559267SweezyCat in a tree (BOI17_catinatree)C++17
51 / 100
1080 ms29104 KiB
#include <bits/stdc++.h> using namespace std; // #define int long long #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif #define all(a) (a).begin(), (a).end() #define rep(i, n) for (int i = 0; i < (n); ++i) #define reps(i, s, n) for (int i = s; i < (n); ++i) #define pb push_back #define sz(a) (int) (a.size()) const int N = 2e5 + 5; const int inf = 1e9; vector<int> g[N]; int s[N], mdist[N], used[N], res, d; vector<pair<int, int>> centroids[N], vs; void sizes(int v, int p) { s[v] = 1; for (auto &u : g[v]) { if (u != p && !used[u]) { sizes(u, v); s[v] += s[u]; } } } int centroid(int v, int p, int n) { for (auto &u : g[v]) { if (u != p && !used[u] && s[u] > n / 2) { return centroid(u, v, n); } } return v; } void add_centroid(int v, int p, int centroid, int dist) { centroids[v].emplace_back(centroid, dist); for (auto &u : g[v]) { if (u != p && !used[u]) { add_centroid(u, v, centroid, dist + 1); } } } void decomposition1(int v) { used[v] = 1; sizes(v, -1); add_centroid(v, -1, v, 0); for (auto &u : g[v]) { if (!used[u]) { decomposition1(centroid(u, v, s[u])); } } } void dfs(int v, int p, int dst) { vs.emplace_back(dst, v); for (auto &u : g[v]) { if (u != p) { dfs(u, v, dst + 1); } } } void decomposition2(int v) { used[v] = 1; sizes(v, -1); vs.clear(); dfs(v, -1, 0); sort(vs.begin(), vs.end()); auto can = [&] (int ver, int dst) -> bool { for (auto &[centroid, dist_to_centroid] : centroids[ver]) { if (dist_to_centroid + mdist[centroid] < d) { return false; } } return true; }; int m = sz(vs), r = m, cnt = 0; rep(l, m) { while (r - 1 >= l && vs[r - 1].first >= max(vs[l].first, d - vs[l].first)) { r--; int ver = vs[r].second; int dst = vs[r].first; if (can(ver, dst)) { cnt++; for (auto &[centroid, dist_to_centroid] : centroids[ver]) { mdist[centroid] = min(mdist[centroid], dist_to_centroid); } } } if (l == r) { res = max(res, cnt); break; } else { res = max(res, cnt + can(vs[l].second, vs[l].first)); } } for (auto &[vd, ver] : vs) { for (auto &[centroid, dist_to_centroid] : centroids[ver]) { mdist[centroid] = inf; } } for (auto &u : g[v]) { if (!used[u]) { decomposition2(centroid(u, v, s[u])); } } } void solve() { fill(mdist, mdist + N, inf); int n; cin >> n >> d; if (d > n - 1) { cout << 1; return; } if (d == 0) { cout << n; return; } reps(i, 1, n) { int p; cin >> p; g[p].push_back(i); g[i].push_back(p); } decomposition1(0); fill(used, used + N, 0); decomposition2(0); cout << res; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...