Submission #571876

#TimeUsernameProblemLanguageResultExecution timeMemory
571876dantoh000Meetings 2 (JOI21_meetings2)C++14
100 / 100
339 ms40592 KiB
#include <bits/stdc++.h> using namespace std; int n; vector<int> G[200005]; int sz[200005]; int p[18][200005]; int d[200005]; int ord[200005]; int ans[200005]; bool cmp(int a, int b){ return sz[a] > sz[b]; } void dfs(int u){ sz[u] = 1; for (auto v: G[u]){ if (v == p[0][u]) continue; p[0][v] = u; d[v] = d[u]+1; dfs(v); sz[u] += sz[v]; } } int dfs2(int u){ for (auto v : G[u]){ if (v == p[0][u]) continue; if (sz[v] > n/2) return dfs2(v); } return u; } int lca(int u, int v){ if (d[u] < d[v]) swap(u,v); int diff = d[u]-d[v]; for (int k = 17; k >= 0; k--){ if (diff>>k&1) u = p[k][u]; } if (u == v) return u; for (int k = 17; k >= 0; k--){ if (p[k][u] && p[k][v] && p[k][u] != p[k][v]){ u = p[k][u]; v = p[k][v]; } } assert(p[0][u] == p[0][v]); return p[0][u]; } int dist(int u, int v){ return d[u] + d[v] - 2*d[lca(u,v)]; } int main(){ scanf("%d",&n); for (int i = 1,u,v; i < n; i++){ scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } dfs(1); int c = dfs2(1); for (int i = 1; i <= n; i++){ p[0][i] = 0; } d[c] = 0; dfs(c); for (int k = 1; k < 18; k++){ for (int i = 1; i <= n; i++){ p[k][i] = p[k-1][p[k-1][i]]; } } iota(ord, ord+n, 1); sort(ord, ord+n, cmp); int end1 = c, end2 = c; int L = 1; for (int i = 0; i < n; i++){ int j = ord[i]; ///printf("%d %d\n",j,sz[j]); int d1 = dist(j, end1) + 1; int d2 = dist(j, end2) + 1; if (d1 < d2){ swap(d1,d2); swap(end1,end2); } if (d1 > L){ L = d1; end2 = j; } ans[sz[j]] = L; } for (int i = n; i >= 1; i--){ ans[i] = max(ans[i], ans[i+1]); } for (int i = 1; i <= n; i++){ if (i%2 == 1) printf("1\n"); else printf("%d\n",ans[i/2]); } }

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
meetings2.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...