Submission #1019254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019254		doducanh	Village (BOI20_village)	C++14	0 / 100	2 ms	4748 KiB

Village

#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 (stderr)

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

• Subtask 1: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50