Submission #914912

#	Time	Username	Problem	Language	Result	Execution time	Memory
914912		alexander707070	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	602 ms	190544 KiB

meetings2

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

struct dude{
    int h,l;
};

int n,a,b,sz[MAXN],root,parent[MAXN],pt[MAXN],ans[MAXN];
int dist[MAXN],maxs,dep[MAXN],from,to,diameter,curr;
vector<int> v[MAXN];
vector<int> rem[MAXN],s;
bool used[MAXN],in[MAXN];

queue<int> q[MAXN];

void dfs(int x,int p,int d){
    sz[x]=1; parent[x]=p; dep[x]=d;

    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        dfs(v[x][i],x,d+1);
        sz[x]+=sz[v[x][i]];
    }
}

int dp[MAXN][20];
bool li[MAXN][20];

int ff(int x,int p){
    if(p==0)return parent[x];
    if(x==0)return 0;

    if(li[x][p])return dp[x][p];
    li[x][p]=true;

    dp[x][p]=ff(ff(x,p-1),p-1);
    return dp[x][p];
}

int getdist(int x,int y){
    int res=0;

    if(dep[x]<dep[y])swap(x,y);

    for(int i=19;i>=0;i--){
        if((1<<i)<=dep[x]-dep[y]){
            x=ff(x,i);
            res+=(1<<i);
        }
    }

    for(int i=19;i>=0;i--){
        if(ff(x,i)!=0 and ff(y,i)!=0 and ff(x,i)!=ff(y,i)){
            res+=2*(1<<i);
            x=ff(x,i); y=ff(y,i);
        }
    }

    if(x!=y)res+=2;

    return res;
}

int centroid(int x,int p){
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        if(sz[v[x][i]]>n/2){
            return centroid(v[x][i],x);
        }
    }

    return x;
}

void dfs1(int x,int p,int d){
    diameter=max(diameter,d);

    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p or !in[v[x][i]])continue;
        dfs1(v[x][i],x,d+1);
    }
}

void add(int x){
    in[x]=true;

    if(from==0){
        from=to=x;
        diameter=0;
        return;
    }

    for(int i=0;i<v[x].size();i++){
        if(in[v[x][i]]){

            curr=getdist(x,from);
            if(curr>diameter){
                diameter=curr;
                to=x;
            }

            curr=getdist(x,to);
            if(curr>diameter){
                diameter=curr;
                from=x;
            }
        }
    }
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dfs(1,0,0);
    root=centroid(1,0);
    dfs(root,0,0);

    for(int i=1;i<=n;i++){
        pt[i]=i; 
        if(v[i].size()==1){
            q[1].push(i);
        }
    }

    for(int k=1;k<=n/2;k++){
        while(!q[k-1].empty()){
            curr=q[k-1].front();

            if(used[curr]){
                q[k-1].pop();
                continue;
            }

            rem[k].push_back(curr);
            used[curr]=true;

            q[sz[parent[curr]]].push(parent[curr]);

            q[k-1].pop();
        }

        reverse(rem[k].begin(),rem[k].end());
    }

    add(root);
    for(int i=1;i<=n;i++){
        if(!used[i] and i!=root){
            add(i);
        }
    }

    for(int k=n/2;k>=1;k--){

        ans[2*k]=diameter+1;

        for(int f:rem[k]){
            add(f);
        }
    }

    for(int i=1;i<=n;i++){
        if(i%2==1)cout<<"1\n";
        else cout<<ans[i]<<"\n";
    }

    return 0;
}

Compilation message (stderr)

meetings2.cpp: In function 'void dfs(int, int, int)':
meetings2.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
meetings2.cpp: In function 'int centroid(int, int)':
meetings2.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
meetings2.cpp: In function 'void dfs1(int, int, int)':
meetings2.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
meetings2.cpp: In function 'void add(int)':
meetings2.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

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