Submission #1215320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215320		nrg_studio	Village (BOI20_village)	C++20	100 / 100	63 ms	14784 KiB

Village

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int MAX_N = 1e5;
vec<int> adj[MAX_N];
int n;

namespace MAXIMUM {
    int sz[MAX_N];
    int to[MAX_N]; ll ans = 0;
    int get_size(int cur, int par=-1) {
        sz[cur] = 1;
        for (int x : adj[cur]) {
            if (x!=par) {
                sz[cur] += get_size(x,cur);
            }
        } return sz[cur];
    }
    int get_cent(int cur, int par=-1) {
        for (int x : adj[cur]) {
            if (x!=par) {
                if (sz[x]*2>n) {return get_cent(x,cur);}
            }
        } return cur;
    }
    ll dep_sum(int cur, int par=-1, int dep=0) {
        ll ret = dep*2;
        for (int x : adj[cur]) {
            if (x!=par) {
                ret += dep_sum(x,cur,dep+1);
            }
        } return ret;
    }
    vec<int> ord;
    void dfs(int cur, int par=-1) {
        ord.pb(cur);
        for (int x : adj[cur]) {
            if (x!=par) {dfs(x,cur);}
        }
    }

    void solve() {
        int cent = get_cent(0,get_size(0));
        get_size(cent);
        ans = dep_sum(cent); dfs(cent);
        for (int i=0;i<n;i++) {to[ord[i]] = ord[(i+n/2)%n];}
    }
}

namespace MINIMUM {
    int to[MAX_N], ans = 0;
    void dfs(int cur, int par=-1) {
        int last = cur;
        for (int x : adj[cur]) {
            if (x!=par) {
                dfs(x,cur);
                if (to[x]==-1) {
                    to[last] = x;
                    ans += 2;
                    last = x;
                }
            }
        }
        if (last!=cur) {to[last] = cur;}
        else if (cur==0) {
            to[0] = to[adj[cur][0]];
            to[adj[cur][0]] = 0;
            ans += 2;
        }
    }
    void solve() {
        memset(to,-1,sizeof(to));
        dfs(0);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n;
    for (int i=0;i<n-1;i++) {
        int a, b; cin >> a >> b;
        adj[--a].pb(--b);
        adj[b].pb(a);
    }
    MINIMUM::solve(); 
    MAXIMUM::solve();
    cout << MINIMUM::ans << ' ' << MAXIMUM::ans << '\n';
    for (int i=0;i<n;i++) {cout << MINIMUM::to[i]+1 << ' ';} cout << '\n';
    for (int i=0;i<n;i++) {cout << MAXIMUM::to[i]+1 << ' ';}
}

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