제출 #559221

#제출 시각아이디문제언어결과실행 시간메모리
559221SweezyCat in a tree (BOI17_catinatree)C++17
11 / 100
1088 ms596 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()) struct Tree { typedef int T; static constexpr T unit = INT_MAX; T f(T a, T b) { return min(a, b); } vector<T> s; int n; Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {} void update(int pos, T val) { for (s[pos += n] = val; pos /= 2;) s[pos] = f(s[pos * 2], s[pos * 2 + 1]); } T query(int b, int e) { T ra = unit, rb = unit; for (b += n, e += n; b < e; b /= 2, e /= 2) { if (b % 2) ra = f(ra, s[b++]); if (e % 2) rb = f(s[--e], rb); } return f(ra, rb); } }; void solve() { int n, d; cin >> n >> d; if (d > n - 1) { cout << 1; return; } if (d == 0) { cout << n; return; } vector<vector<int>> g(n); reps(i, 1, n) { int p; cin >> p; g[p].push_back(i); g[i].push_back(p); } int timer = 0; vector<pair<int, int>> vs; vector<int> tin(n), tout(n), par(n); function<void(int, int, int)> dfs = [&] (int v, int p, int dst) { par[v] = p; tin[v] = timer++; vs.emplace_back(dst, v); for (auto &u : g[v]) { if (u != p) { dfs(u, v, dst + 1); } } tout[v] = timer; }; int res = 0; rep(root, n) { // debug(root); timer = 0; vs.clear(); dfs(root, -1, 0); sort(vs.begin(), vs.end()); // debug(vs); Tree st(n); int r = n, cnt = 0; auto can = [&] (int v, int dst) -> bool { bool ok = 1; int dv = 0; while (v != -1) { int dst_subtree = st.query(tin[v], tout[v]); ok &= dst_subtree - dst + dv >= d; dv++; dst--; v = par[v]; } return ok; }; rep(l, n) { while (r - 1 >= l && vs[r - 1].first >= max(vs[l].first, d - vs[l].first)) { r--; int v = vs[r].second; int dst = vs[r].first; if (can(v, dst)) { cnt++; st.update(tin[v], dst); } } // debug(l, r, cnt); if (l == r) { res = max(res, cnt); break; } else { res = max(res, cnt + can(vs[l].second, vs[l].first)); } } // debug(res); } // vector<vector<int>> dp(n, vector<int> (n)); // function<void(int)> dfs = [&] (int v) { // for (auto &u : g[v]) { // dfs(u); // } // debug(v); // // v is off // for (int dist = 1; dist <= d; dist++) { // debug(dist); // for (auto &u : g[v]) { // int tr = dp[u][dist - 1]; // int other = max(dist, d - dist); // for (auto &w : g[v]) { // if (w != u) { // tr += dp[w][other - 1]; // } // } // dp[v][dist] = max(dp[v][dist], tr); // } // } // // v is on // int tr = 0; // for (auto &u : g[v]) { // tr += dp[u][d - 1]; // } // debug(v, tr); // dp[v][0] = max(dp[v][0], 1 + tr); // for (int dist = d - 1; dist >= 0; dist--) { // dp[v][dist] = max(dp[v][dist], dp[v][dist + 1]); // } // // reps(dist, 1, n) { // // dp[v][dist] = max(dp[v][dist], dp[v][dist - 1]); // // } // debug(v, dp[v]); // }; // dfs(0); // int res = 0; // rep(i, n) { // rep(dist, d + 1) { // res = max(res, dp[i][dist]); // } // } 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...