Submission #973386

#	Time	Username	Problem	Language	Result	Execution time	Memory
973386		MarwenElarbi	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	2 ms	6748 KiB

meetings2

#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(cen,-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)
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80