Submission #973384

#TimeUsernameProblemLanguageResultExecution timeMemory
973384MarwenElarbiMeetings 2 (JOI21_meetings2)C++17
0 / 100
2 ms7000 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define pb push_back const int nax=2e5+5; int bj[nax][20]; int dep[nax]; int sz[nax]; vector<int> adj[nax]; int n; void get_size(int x,int p){ sz[x]=1; for(auto u:adj[x]){ if(u==p) continue; bj[u][0]=x; dep[u]=dep[x]+1; get_size(u,x); sz[x]+=sz[u]; } return; } int centroid(int x,int p){ for(auto u:adj[x]){ if(u==p) continue; if(sz[u]*2>n) return centroid(u,x); } return x; } void build(int x,int p){ for (int i = 1; i < 20; ++i) { bj[x][i]=bj[bj[x][i-1]][i-1]; } for(auto u:adj[x]){ if(u==p) continue; build(u,x); } } int jump(int x,int d){ for (int i = 0; i < 20; ++i) { if(d&(1<<i)) x=bj[x][i]; } return x; } int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); x=jump(x,dep[x]-dep[y]); if(x==y) return x; for (int i = 19; i >= 0; --i) { int curx=bj[x][i]; int cury=bj[y][i]; if(cury!=curx){ x=curx; y=cury; } } return bj[x][0]; } int dis(int x,int y){ return dep[x]+dep[y]-2*dep[lca(x,y)]+1; } int main(){ cin>>n; for (int i = 0; i < n-1; ++i) { int x,y; cin>>x>>y; x--;y--; adj[x].pb(y); adj[y].pb(x); } get_size(0,-1); int cen=centroid(0,-1); dep[cen]=0; bj[cen][0]=cen; get_size(cen,-1); build(0,-1); vector<int> tab[n+1]; for (int i = 0; i < n; ++i) { tab[sz[i]].pb(i); } int a=cen; int b=cen; int ans=0; int res[n]; //cout <<dep[4]<<" "<<dep[0]<<" "<<lca(0,4)<<endl; for (int i = n/2; i >=1 ; --i) { //cout <<"nabba"<<" "<<i<<endl; for (int j = 0; j < tab[i].size(); ++j) { //cout <<tab[i][j]<<endl; int nw=tab[i][j]; int x=dis(nw,a); int y=dis(nw,b); //cout <<x<<" "<<y<<" "<<a<<" "<<b<<endl; if(ans<y){ a=nw; ans=y; } if(ans<x){ b=nw; ans=x; } }//cout <<endl; res[i]=ans; } for (int i = 1; i <= n; ++i) { if(i%2) cout <<1<<endl; else cout <<res[i/2]<<endl; } }

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int j = 0; j < tab[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...