oj.uz

Submission #1019255

# Submission time Handle Problem Language Result Execution time Memory
1019255 2024-07-10T16:13:11 Z doducanh Village (BOI20_village) C++14
0 / 100
 1 ms 4696 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+7;
int subtree[maxn];
int dd[maxn];
int ans[maxn];
vector<int>a[maxn];
int n,c;
vector<int>v;
int cnt=0;
int cha;
int dfs(int u,int par){
    subtree[u]=1;
    for(int v:a[u])if(v!=par){
        subtree[u]+=dfs(v,u);
        cnt+=min(subtree[v],n-subtree[v]);
    }
    return subtree[u];
}
int get_cen(int u,int par){
    for(int v:a[u])if(v!=par){
        if(2*subtree[v]>n)return get_cen(v,u);
    }
    cha=(par==0?a[u][0]:par);
    return u;
}
void dfs2(int u,int par){
    v.push_back(u);
    dd[u]=1;
    for(int v:a[u])if(v!=par){
        dfs2(v,u);
    }
}
main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1,0);
    c=get_cen(1,0);
    dfs2(c,cha);
    for(int i=1;i<=n;i++)if(dd[i]==0)v.push_back(i);
//    for(int x:v)cout<<x<<" ";
//    cout<<"\n";
    for(int i=0;i<n;i++){
        ans[v[i]]=v[(i+n/2)%n];
    }
    cout<<2*cnt<<"\n";
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}

Compilation message

Village.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main(){
      | ^~~~

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4696 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4696 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4696 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -