Submission #667747

#TimeUsernameProblemLanguageResultExecution timeMemory
667747dutinmeowCat in a tree (BOI17_catinatree)C++17
100 / 100
350 ms35152 KiB
#include <bits/stdc++.h> namespace std { template<class Fun> class y_combinator_result { Fun fun_; public: template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {} template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); } }; template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); } } // namespace std struct heavy_light_decomposition { std::vector<int> par, dep, hed, tin; heavy_light_decomposition(int R, std::vector<std::vector<int>> T) { int n = (int)T.size(), time = 0; par.resize(n), dep.resize(n); hed.resize(n), tin.resize(n); par[R] = -1, dep[R] = 0, hed[R] = R; std::y_combinator([&](auto self, int u) -> int { int sub = 1, mxs = 0; for (int &v : T[u]) { if (v == par[u]) continue; par[v] = u; dep[v] = dep[u] + 1; int t = self(v); sub += t; if (mxs < t) { mxs = t; std::swap(T[u].front(), v); } } return sub; })(R); std::y_combinator([&](auto self, int u) -> void { tin[u] = time++; for (int v : T[u]) { if (v == par[u]) continue; hed[v] = v == T[u].front() ? hed[u] : v; self(v); } })(R); } int lowest_common_ancestor(int u, int v) { for (; hed[u] != hed[v]; u = par[hed[u]]) if (dep[hed[u]] < dep[hed[v]]) std::swap(u, v); return dep[u] < dep[v] ? u : v; } int distance(int u, int v) { return dep[u] + dep[v] - 2 * dep[lowest_common_ancestor(u, v)]; } }; class centroid_decomposition { int n; std::vector<std::vector<int>> tree; std::vector<int> parent, weight; std::vector<bool> block; int initialize_weight(int u, int p) { weight[u] = 1; for (int v : tree[u]) { if (p == v || block[v]) continue; weight[u] += initialize_weight(v, u); } return weight[u]; } int find_centroid(int w, int u, int p) { for (int v : tree[u]) { if (p == v || block[v]) continue; if (2 * weight[v] > w) return find_centroid(w, v, u); } return u; } void initialize_centroids(int c, int p) { int w = initialize_weight(c, -1); c = find_centroid(w, c, -1); parent[c] = p; block[c] = true; for (int v : tree[c]) { if (block[v]) continue; initialize_centroids(v, c); } } public: centroid_decomposition(const std::vector<std::vector<int>> &_tree) : n((int)_tree.size()), tree(_tree) { parent.resize(n); weight.resize(n); block.assign(n, false); initialize_centroids(0, -1); } int operator[](int i) { return parent[i]; } }; int main() { using namespace std; int N, D; cin >> N >> D; vector<vector<int>> T(N); for (int i = 1; i < N; i++) { int p; cin >> p; T[i].push_back(p); T[p].push_back(i); } heavy_light_decomposition hld(0, T); centroid_decomposition cd(T); vector<int> ord(N); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&hld](int a, int b) { return hld.dep[a] > hld.dep[b]; }); vector<int> ans; vector<int> dis(N, (int)1e9); for (int s : ord) { int cur = (int)1e9; for (int t = s; t != -1; t = cd[t]) cur = min(cur, dis[t] + hld.distance(s, t)); if (cur >= D) { ans.push_back(s); for (int t = s; t != -1; t = cd[t]) { dis[t] = min(dis[t], hld.distance(s, t)); } } } cout << ans.size() << '\n'; // for (int u : ans) // cout << u + 1 << ' '; // cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...