oj.uz

Submission #914880

# Submission time Handle Problem Language Result Execution time Memory
914880 2024-01-22T20:06:52 Z alexander707070 Meetings 2 (JOI21_meetings2) C++14
0 / 100
 6 ms 22876 KB 
#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,dep[MAXN],from,to,diameter;
vector<int> v[MAXN];
vector<int> rem[MAXN],s;
bool used[MAXN],in[MAXN];

unordered_set<int> active;

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){
    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);
    }
}

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]]){
            if(getdist(x,from)>diameter){
                diameter=getdist(x,from);
                to=x;
            }

            if(getdist(x,to)>diameter){
                diameter=getdist(x,to);
                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; 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.push_back(pt[i]);
                    break;
                }
                
                rem[k].push_back(pt[i]);
                used[pt[i]]=true;
                pt[i]=parent[pt[i]];
            }
        }

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

        for(int i:s){
            active.erase(i);
        }
        s.clear();
    }

    for(int i=1;i<=n;i++){
        if(!used[i])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

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18776 KB Output is correct
2 Correct 6 ms 22872 KB Output is correct
3 Incorrect 6 ms 22876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18776 KB Output is correct
2 Correct 6 ms 22872 KB Output is correct
3 Incorrect 6 ms 22876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18776 KB Output is correct
2 Correct 6 ms 22872 KB Output is correct
3 Incorrect 6 ms 22876 KB Output isn't correct
4 Halted 0 ms 0 KB -