Submission #1204693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204693		Unforgettablepl	Village (BOI20_village)	C++20	100 / 100	69 ms	14876 KiB

Village

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

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<int>> adj(N+1);
    for(int i=1;i<N;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    int answer1 = 0;
    vector<int> answer1vec(N+1);
    {
        // answer 1
        int centroid = -1;
        {
            auto dfs = [&](auto&& self,int x,int p)->int{
                int siz = 1;
                for(int&i:adj[x])if(i!=p)siz+=self(self,i,x);
                if((N-siz)<=N/2){
                    centroid = x;
                    return -1e10;
                }
                return siz;
            };
            dfs(dfs,1,0);
        }
        vector<int> curr(N+1);
        int idx = -1;
        auto dfs = [&](auto&& self,int x,int p,int dep)->void{
            if(++idx>N/2){
                answer1vec[curr[idx-N/2]]=x;
                answer1vec[x]=curr[idx-N/2];
            } else curr[idx]=x;
            answer1+=2ll*dep;
            for(int&i:adj[x])if(i!=p)self(self,i,x,dep+1);
        };
        dfs(dfs,centroid,0,0);
        if(N&1){
            answer1vec[centroid]=answer1vec[curr[1]];
            answer1vec[curr[1]]=centroid;
        } else {
            answer1vec[curr[N/2]]=centroid;
            answer1vec[centroid]=curr[N/2];
        }
    }
    int answer2 = 0;
    vector<int> answer2vec(N+1);
    {
        iota(answer2vec.begin(),answer2vec.end(),0);
        auto addInChain = [&](int x,int y){
            answer2vec[y]=answer2vec[x];
            return answer2vec[x]=y;
        };
        auto dfs = [&](auto&& self,int x,int p)->bool{
            vector<int> childrenNeeding;
            for(int&i:adj[x])if(i!=p){
                if(self(self,i,x))childrenNeeding.emplace_back(i);
            }
            if(childrenNeeding.empty())return true;
            int last = x;
            for(int&i:childrenNeeding)last=addInChain(last,i);
            answer2+=(int)childrenNeeding.size()*2ll;
            return false;
        };
        if(dfs(dfs,1,0)){
            addInChain(adj[1][0],1);
            answer2+=2;
        }
    }
    cout << answer2 << ' ' << answer1 << '\n';
    for(int i=1;i<=N;i++)cout<<answer2vec[i]<<' ';
    cout << '\n';
    for(int i=1;i<=N;i++)cout<<answer1vec[i]<<' ';
    cout << '\n';
}

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