Submission #395653

#TimeUsernameProblemLanguageResultExecution timeMemory
395653usachevd0Meetings 2 (JOI21_meetings2)C++17
100 / 100
840 ms29520 KiB
/*#pragma gcc optimize("Ofast") #pragma gcc optimize("O3") #pragma gcc optimize("fast-math") #pragma gcc optimize("unroll-loops") #pragma gcc optimize("no-stack-protector") #pragma gcc target("avx,avx2,ffa,sse,sse2,sse4.2")*/ #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) { cerr << a[i] << ' '; } cerr << endl; } #ifdef DEBUG #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) { for (auto& x : v) { stream << x << ' '; } return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << "(" << p.first << ' ' << p.second << ")"; } const int INF32 = 1e9; const int maxN = 200005; int n; vector<int> G[maxN]; int ans[maxN]; bool used[maxN]; int depth[maxN]; int sz[maxN]; int max_depth[maxN]; pii max_depth_1[maxN], max_depth_2[maxN]; int find_centroid(int v, int SZ, int& c, int p = -1) { int sz = 1; for (int& u : G[v]) { if (u != p && !used[u]) { sz += find_centroid(u, SZ, c, v); } } if (c == -1 && sz + sz >= SZ) { c = v; } return sz; } void rec(int v, int d = 0, int p = -1) { depth[v] = d; sz[v] = 1; for (int& u : G[v]) { if (u != p && !used[u]) { rec(u, d + 1, v); sz[v] += sz[u]; } } chkmax(max_depth[sz[v]], depth[v]); } void build(int v0, int SZ) { int c = -1; find_centroid(v0, SZ, c); if (c == -1) { c = v0; } //debug(c); depth[c] = 0; fill(max_depth_1, max_depth_1 + SZ + 1, mp(-INF32, -1)); fill(max_depth_2, max_depth_2 + SZ + 1, mp(-INF32, -2)); int subtrees = 0; for (int v : G[c]) { if (!used[v]) { ++subtrees; rec(v, 1, c); sz[c] += sz[v]; //debug(v); //mdebug(max_depth, sz[v] + 1); for (int s = 1; s <= sz[v]; ++s) { chkmax(ans[min(s, SZ - sz[v])], max_depth[s]); } for (int s = 1; s <= sz[v]; ++s) { if (max_depth[s] >= max_depth_1[s].fi) { max_depth_2[s] = max_depth_1[s]; max_depth_1[s] = {max_depth[s], v}; } else chkmax(max_depth_2[s], mp(max_depth[s], v)); } fill(max_depth, max_depth + sz[v] + 1, -INF32); } } //mdebug(max_depth_1, sz[c] + 1); //mdebug(max_depth_2, sz[c] + 1); if (subtrees >= 2) { for (int s = SZ - 1; s >= 0; --s) { for (pii A : {max_depth_1[s + 1], max_depth_2[s + 1]}) { if (A.fi >= max_depth_1[s].fi) { if (max_depth_1[s].se != A.se) { max_depth_2[s] = max_depth_1[s]; } max_depth_1[s] = A; } else if (A.fi > max_depth_2[s].fi && max_depth_1[s].se != A.se) { max_depth_2[s] = A; } } } //mdebug(max_depth_1, sz[c] + 1); //mdebug(max_depth_2, sz[c] + 1); for (int v : G[c]) { if (!used[v]) { rec(v, 1, c); for (int s = 1; s <= sz[v]; ++s) { int d1 = max_depth[s]; int d2 = max_depth_1[s].se != v ? max_depth_1[s].fi : max_depth_2[s].fi; //debug(v, s, d1, d2); chkmax(ans[s], d1 + d2); } fill(max_depth, max_depth + sz[v] + 1, -INF32); } } } used[c] = true; for (int v : G[c]) { if (!used[v]) { build(v, sz[v]); } } } int32_t main() { #ifdef DEBUG freopen("in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; G[a].pb(b); G[b].pb(a); } fill(max_depth, max_depth + n + 1, -INF32); build(1, n); for (int s = n; s >= 0; --s) { chkmax(ans[s], ans[s + 1]); } for (int k = 1; k <= n; ++k) { if (k & 1) { cout << "1\n"; } else { cout << ans[k / 2] + 1 << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...