Submission #724975

#TimeUsernameProblemLanguageResultExecution timeMemory
724975piOOEMeetings 2 (JOI21_meetings2)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<vector<int>> adj(n); vector<int> parent(n), siz(n), depth(n); for (int i = 1; i < n; ++i) { int a, b; cin >> a >> b; a -= 1, b -= 1; adj[a].push_back(b); adj[b].push_back(a); } auto hld = [&](auto self, int v) -> void { siz[v] = 1; for (int &to : adj[v]) { adj[to].erase(find(adj[to].begin(), adj[to].end(), v)); depth[to] = depth[v] + 1; self(self, to); siz[v] += siz[to]; if (siz[to] > siz[adj[v][0]]) { swap(to, adj[v][0]); } } }; hld(hld, 0); vector<map<int, int>> st(n); auto insert = [&](map<int, int> &mp, int x, int y) -> void { auto it = mp.lower_bound(x); if (it != mp.end() && it->second >= y) { return; } mp[x] = y; while (true) { it = mp.lower_bound(x); if (it == mp.begin() || prev(it)->second > y) { break; } mp.erase(prev(it)); } }; constexpr int inf = 1e8 + 7; auto query = [&](map<int, int> &mp, int x) { auto it = mp.lower_bound(x); return it == mp.end() ? -inf : it->second; }; vector<int> best(n + 1); auto dfs = [&](auto self, int v) -> void { if (adj[v].empty()) { insert(st[v], 1, depth[v]); return; } for (int to : adj[v]) { self(self, to); } int x = adj[v][0]; int now = min(siz[x], n - siz[x]); int nxt = 0; for (int s = now; s > nxt; --s) { int d = query(st[x], s); best[min(s, n - siz[x])] = max(best[min(s, n - siz[x])], d - depth[v] + 1); } swap(st[v], st[x]); for (int to : adj[v]) { if (to == x) { continue; } for (int s = 1; s <= siz[to]; ++s) { int d = query(st[to], s); best[s] = max(best[s], d + query(st[v], s) - depth[v] * 2 + 1); best[min(s, n - siz[to])] = max(best[min(s, n - siz[to])], d - depth[v] + 1); } for (auto [a, b] : st[to]) { insert(st[v], a, b); } st[to].clear(); } insert(st[v], siz[v], depth[v]); }; dfs(dfs, 0); vector<int> ans(n + 1, 1); for (int i = 1; i <= n / 2; ++i) { assert(best[i]); ans[i * 2] = best[i]; } for (int i = 1; i <= n; ++i) { cout << ans[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...