Submission #549990

#TimeUsernameProblemLanguageResultExecution timeMemory
549990hohohahaMeetings 2 (JOI21_meetings2)C++14
100 / 100
251 ms94284 KiB
#include<bits/stdc++.h> using namespace std; #define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) #define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) #define ii pair<int, int> #define fi first #define se second #define vi vector<int> #define eb emplace_back #define em emplace #define sp ' ' #define endl '\n' #define int long long const int maxn =2e5 +5; int n; vi g[maxn]; int tim; int tin[maxn]; int dep[maxn]; int sz[maxn]; int euler[maxn * 2]; int lca[21][maxn * 2]; vector<int> nodes_sz[maxn]; pair<int, ii> Dia; int ans[maxn]; void dfs_sz(int u, int p) { sz[u] = 1; for(int v: g[u]) { if(v - p) { dfs_sz(v, u); sz[u] += sz[v]; } } } int get_cen(int u, int p) { for(int v: g[u]) { if(v - p and sz[v] * 2 > sz[1]) return get_cen(v, u); } return u; } void dfs_prep(int u, int p) { sz[u] = 1; ++tim; tin[u] = tim; euler[tim] = u; for(int v: g[u]) { if(v - p) { dep[v] = dep[u] + 1; dfs_prep(v, u); sz[u] += sz[v]; ++tim; euler[tim] = u; } } } int hg(int u, int v) { return dep[u] < dep[v]? u: v; } int get_lca(int u, int v) { int l = tin[u], r = tin[v]; if(r < l) swap(r, l); int bit = __lg(r - l + 1); return hg(lca[bit][l], lca[bit][r - (1 << bit) + 1]); } int get_dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[get_lca(u, v)]; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; fori(i, 2, n) { int u, v; cin >> u >> v; g[u].eb(v); g[v].eb(u); } dfs_sz(1, 1); int cen = get_cen(1, 1); dfs_prep(cen, cen); // cout << cen << endl; fori(bit, 0, 20) { fori(i, 1, tim - (1 << bit) + 1) { lca[bit][i] = !bit? euler[i]: hg(lca[bit - 1][i], lca[bit - 1][i + (1 << bit - 1)]); } } // cout << get_dis(1, 5) << endl; fori(i, 1, n) nodes_sz[sz[i]].eb(i); Dia = make_pair(0, ii(cen, cen)); int pt = n; ford(j, n, 1) { if(j & 1) ans[j] = 1; else { for(; pt >= j / 2; pt--) { for(int u: nodes_sz[pt]) { // cout << pt << ": " << u << endl; int l = Dia.se.fi, r = Dia.se.se; Dia = max({Dia, make_pair(get_dis(l, u), ii(l, u)), make_pair(get_dis(u, r), ii(u, r))}); } } ans[j] = 1 + Dia.fi; } } fori(i, 1, n) cout << ans[i] << endl; }

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:95:81: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   95 |    lca[bit][i] = !bit? euler[i]: hg(lca[bit - 1][i], lca[bit - 1][i + (1 << bit - 1)]);
      |                                                                             ~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...