제출 #649175

#제출 시각아이디문제언어결과실행 시간메모리
649175LeonaRagingCat in a tree (BOI17_catinatree)C++14
0 / 100
4 ms5716 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define pb push_back #define db(val) "[" #val " = " << (val) << "] " const ll mod = 1e9 + 7; const int maxn = 2e5 + 4; const int INF = 1e9; const int N = 18; int n, d, h[maxn], up[maxn][20], par[maxn], mn[maxn]; vector<int> adj[maxn], nodes; bool used[maxn]; void dfs(int u, int p) { up[u][0] = p; for (int j = 1; j <= N; j++) up[u][j] = up[up[u][j - 1]][j - 1]; for (int v : adj[u]) if (v != p) { h[v] = h[u] + 1; dfs(v, u); } } int lca(int u, int v) { if (h[u] < h[v]) swap(u, v); int k = h[u] - h[v]; for (int j = N; j >= 0; j--) if (k >> j & 1) u = up[u][j]; if (u == v) return u; for (int j = N; j >= 0; j--) if (up[u][j] != up[v][j]) u = up[u][j], v = up[v][j]; return up[u][0]; } int dis(int u, int v) { return h[u] + h[v] - 2 * h[lca(u, v)]; } void update(int u) { for (int v = u; v != 0; v = par[v]) mn[v] = min(mn[v], dis(v, u)); } bool ok(int u) { for (int v = u; v != 0; v = par[v]) { if (mn[v] + dis(u, v) < d) return 0; } return 1; } struct Centroid_Decomposition { int sz[maxn]; int dfs(int u) { sz[u] = 1; for (int v : adj[u]) if (v != up[u][0] && !used[v]) sz[u] += dfs(v); return sz[u]; } int Centroid(int u, int tot) { for (int v : adj[u]) if (v != up[u][0] && !used[v] && sz[v] > tot / 2) return Centroid(v, tot); return u; } void build(int u = 1) { int c = Centroid(u, dfs(u)); used[c] = 1; for (int v : adj[c]) if (!used[v]) { par[v] = c; build(v); } } } Cen; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen(".INP", "r", stdin); //freopen(".OUT", "w", stdout); cin >> n >> d; for (int u = 2; u <= n; u++) { int v; cin >> v; v++; adj[u].pb(v); adj[v].pb(u); } dfs(1, 0); Cen.build(); for (int u = 1; u <= n; u++) nodes.pb(u); sort(nodes.begin(), nodes.end(),[&](int u, int v) { return h[u] > h[v]; }); int res = 0; memset(mn, 63, sizeof mn); for (int u : nodes) { if (ok(u)) { res++; update(u); } } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...