Submission #914874

#	Time	Username	Problem	Language	Result	Execution time	Memory
914874		alexander707070	Meetings 2 (JOI21_meetings2)	C++14	20 / 100	564 ms	28844 KiB

meetings2

#include<bits/stdc++.h>
#define MAXN 300007
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,rem[MAXN];
vector<int> v[MAXN];
bool used[MAXN];

unordered_set<int> active,s;

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

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

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){
    dist[x]=d;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p or used[v[x][i]])continue;
        dfs1(v[x][i],x,d+1);
    }
}

int diameter(){
    for(int i=1;i<=n;i++){
        if(used[i])continue;
        dfs1(i,0,0); break;
    }

    maxs=0;
    for(int i=1;i<=n;i++){
        if(used[i])continue;
        if(dist[i]>dist[maxs])maxs=i;
    }
    
    dfs1(maxs,0,0);

    maxs=0;
    for(int i=1;i<=n;i++){
        if(used[i])continue;
        maxs=max(maxs,dist[i]);
    }

    return maxs+1;
}

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);
    root=centroid(1,0);
    dfs(root,0);

    for(int i=1;i<=n;i++){
        pt[i]=i; active.insert(i);
    }

    for(int k=1;k<=n/2;k++){

        for(int i:active){
            while(sz[pt[i]]<k){

                if(used[pt[i]]){
                    s.insert(i); break;
                }
                
                used[pt[i]]=true;
                pt[i]=parent[pt[i]];
            }
        }

        for(int i:s){
            rem[i]=k;
            active.erase(i);
        }
        s.clear();

        if(n<=4000)ans[2*k]=diameter();
    }

    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)':
meetings2.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
meetings2.cpp: In function 'int centroid(int, int)':
meetings2.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
meetings2.cpp: In function 'void dfs1(int, int, int)':
meetings2.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

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