Submission #1204673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204673		Unforgettablepl	Village (BOI20_village)	C++20	50 / 100	40 ms	11824 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,1);
    {

    }
    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: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50