Submission #971795

#TimeUsernameProblemLanguageResultExecution timeMemory
971795vjudge1Meetings 2 (JOI21_meetings2)C++14
100 / 100
314 ms27248 KiB
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define ld long double #define pb push_back #define pf push_front #define vi vector<ll> #define vii vector<vi> #define pll pair<ll,ll> #define vpll vector<pll> #define all(a) a.begin(), a.end() #define fi first #define se second using namespace std; const ll mod = 1e9+7; const ll inf = 1e18; const ll base = 26; const ll blocksz = 100; const ll N = 2e5+8; const ll lim = 1e5+8; ll sz[N],h[N],mx[N],nmx[N],ans[N],n; vi g[N]; bool del[N]; void cc(ll u, ll p){ sz[u] = 1; for(ll v:g[u]){ if(v == p || del[v]) continue; cc(v,u); sz[u] += sz[v]; } } ll centroid(ll u, ll p, ll siz){ for(ll v:g[u]){ if(v != p && !del[v] && sz[v] > siz/2){ return centroid(v,u,siz); } } return u; } void dfs(ll u, ll p){ sz[u] = 1; for(ll v:g[u]){ if(v != p && !del[v]){ h[v] = h[u]+1; dfs(v,u); sz[u] += sz[v]; } } nmx[sz[u]] = max(nmx[sz[u]],h[u]); } void decompose(ll u){ cc(u,u); ll c = centroid(u,u,sz[u]); h[c] = 1; ll reset = 0; for(ll v:g[c]){ if(!del[v]){ h[v] = h[c]+1; dfs(v,c); reset = max(reset,sz[v]); for(ll i = sz[v]; i >= 0; i--) nmx[i] = max(nmx[i],nmx[i+1]); for(ll i = sz[v]; i >= 0; i--){ ans[i<<1] = max(ans[i<<1],max(1LL,mx[i])+nmx[i]-1); } for(ll i = sz[v]; i >= 0; i--){ mx[i] = max(mx[i],nmx[i]); nmx[i] = 0; } } } for(ll i = 0; i <= reset; i++) mx[i] = 0; del[c] = 1; for(ll v:g[c]) if(!del[v]) decompose(v); } void solve(){ cin >> n; for(ll i = 1; i < n; i++){ ll u,v;cin >> u >> v; g[u].pb(v); g[v].pb(u); } for(ll i = 1; i <= n; i++) ans[i] = 1; decompose(1); for(ll i = 1; i <= n; i++) cout << ans[i] << '\n'; } signed main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); if(fopen("test.inp","r")){ freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } int T = 1; // cin >> T; for(int tt = 1; tt <= T; tt++){ solve(); cout << '\n'; } }

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...