제출 #1125485

#제출 시각아이디문제언어결과실행 시간메모리
1125485duckindogCat in a tree (BOI17_catinatree)C++17
0 / 100
1096 ms5696 KiB
#include <bits/stdc++.h> using namespace std; const int N = 200'000 + 10; int n, d; vector<int> ad[N]; int depth[N]; int f[N][18], st[N], ed[N], it; void dfs0(int u, int p = -1) { st[u] = ++it; for (int i = 1; i <= 17; ++i) f[u][i] = f[f[u][i - 1]][i - 1]; for (const auto& v : ad[u]) { if (v == p) continue; depth[v] = depth[u] + 1; f[v][0] = u; dfs0(v, u); } ed[u] = it; } inline bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; } int lca(int u, int v) { if (anc(u, v)) return u; if (anc(v, u)) return v; for (int i = 17; i >= 0; --i) if (!anc(f[u][i], v)) u = f[u][i]; return f[u][0]; } inline int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } bool mk[N]; int sz[N], totalSize; void initDFS(int u, int p = -1) { sz[u] = 1; for (const auto& v : ad[u]) { if (v == p || mk[v]) continue; initDFS(v, u); sz[u] += sz[v] + 1; } totalSize = sz[u]; } int centroid(int u, int p = -1) { for (const auto& v : ad[u]) { if (v == p || mk[v]) continue; if (sz[v] > totalSize / 2) return centroid(v, u); } return u; } int par[N]; void dfs(int u, int p = -1) { initDFS(u, p); mk[u = centroid(u, p)] = true; par[u] = p; for (const auto& v : ad[u]) { if (v == p || mk[v]) continue; dfs(v, u); } } int minDist[N]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> d; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; ad[u].push_back(v); ad[v].push_back(u); } dfs0(f[1][0] = 1); vector<int> vt(n); iota(vt.begin(), vt.end(), 1); sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { return depth[a] > depth[b]; }); dfs(1); memset(minDist, 63, sizeof minDist); vector<int> answer; for (const auto& i : vt) { int v = i; int minDistance = 1'000'000; while (v != -1) { minDistance = min(minDistance, minDist[v] + dist(i, v)); v = par[v]; } if (minDistance < d) continue; answer.push_back(i); v = i; while (v != -1) { minDist[v] = min(minDist[v], dist(i, v)); v = par[v]; } } cout << answer.size() << "\n"; for (const auto& x : answer) cout << x << " "; cout << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...