Submission #1225650

#TimeUsernameProblemLanguageResultExecution timeMemory
1225650Double_SlashMeetings 2 (JOI21_meetings2)C++20
0 / 100
5 ms9800 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() using pint = pair<int, int>; int n, sz[200001], ans[200001]; vector<int> adj[200001], mx[200001]; vector<pint> order; bool seen[200001]; int dfs(int i, int p = 0) { int m = 0; for (int j: adj[i]) { if (j != p) m |= dfs(j, i); } order.emplace_back(-__builtin_ctz(++m), i); return m; } int dfs2(int i, int root, int d = 1, int p = 0) { int sum = sz[i]; for (int j: adj[i]) { if (j == p or seen[j]) continue; sum += dfs2(j, root, d + 1, i); } if (sum >= mx[root].size()) mx[root].resize(sum + 1); mx[root][sum] = max(mx[root][sum], d); return sum; } int main() { cin >> n; for (int i = n; --i;) { int a, b; cin >> a >> b; adj[a].emplace_back(b); adj[b].emplace_back(a); } dfs(1); sort(all(order)); fill(sz + 1, sz + 1 + n, 1); auto chmax = [] (auto &a, auto b) { a = max(a, b); }; for (auto [m, i]: order) { int tot = seen[i] = true; vector<int> cur{0}; for (int j: adj[i]) { if (seen[j]) continue; tot += dfs2(j, j); for (int k = mx[j].size(); --k;) chmax(mx[j][k - 1], mx[j][k]); for (int k = min(cur.size(), mx[j].size()); --k;) chmax(ans[k << 1], cur[k] + mx[j][k]); if (mx[j].size() > cur.size()) cur.resize(mx[j].size()); for (int k = mx[j].size(); --k;) chmax(cur[k], mx[j][k]); } for (int j: adj[i]) { if (seen[j]) continue; for (int k = mx[j].size(); --k;) chmax(ans[min(k, tot - ((int) mx[j].size() - 1)) << 1], mx[j][k]); sz[j] += tot - (mx[j].size() - 1); mx[j].clear(); } } for (int i = 1; i <= n; ++i) cout << ans[i] + 1 << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...