Submission #1135300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135300		mmdrzada	Village (BOI20_village)	C++20	100 / 100	84 ms	27748 KiB

Village

// Village
// Alphine walley


#include <bits/stdc++.h>

using namespace std;

#define int long long

#define vi vector<int>
#define REP(i, k) for(int i = 0 ; i < k ; i ++)
#define pb push_back
#define pii pair<int, int>
#define ll long long
#define sep ' '
#define F first
#define S second


const int N = 1e5+10;
int n;
vi adj[N];
bool used[N];
int ans[N];
int in[N];
int cnt = 0;
int sum = 0;
int sz[N];
vi V, V2;
int h[N];
bool good[N];
vi vert[N];

void gfs(int v, int p) {
    V.pb(v);
    for(int neigh: adj[v]) {
        if (neigh != p) gfs(neigh, v);
    }
}


void dfs(int v = 0, int p = -1) {
    if (p != -1)
        adj[v].erase(find(adj[v].begin(), adj[v].end(), p));
    h[v] = (p == -1 ? 0 : h[p]+1);
    sz[v]++;
    vi vec;
    for(int neigh: adj[v]) {
        dfs(neigh, v);
        sz[v] += sz[neigh];
        if (!used[neigh]) vec.pb(neigh);
    }
    
    sum += min(sz[v], n-sz[v]);

    if (!vec.empty()) {
        used[v] = true;
        ans[v] = vec.front();
        for(int i = 0 ; i < vec.size()-1 ; i ++) ans[vec[i]] = vec[i+1];
        ans[vec.back()] = v;
        in[v] = vec.back();
        cnt++;
    } else {
        if (v == 0) {
            int u = adj[v].front();
            ans[v] = u;
            ans[in[u]] = v;
        }
    }
}



void solve() {
    cin >> n;
    vector<array<int, 2>> E;
    REP(i, n-1) {
        int a, b; cin >> a >> b; a--, b--;
        adj[a].pb(b), adj[b].pb(a);
        E.pb({a, b});
    }
    dfs();
    cout << 2*(n-1) - 2*(cnt-1) << sep << 2*sum << '\n';
    for(int i = 0 ; i < n ; i ++) cout << ans[i]+1 << sep;
    cout << '\n';
    fill(good, good+n, true);
    REP(i, n) {
    	adj[i].clear();
    }
    for(auto [u, v]: E) adj[u].pb(v), adj[v].pb(u);
    
    for(auto [u, v]: E) {
        if (h[u] > h[v]) swap(u, v);
        if (n%2 == 0 && sz[v]*2 == n) {

            gfs(v, u);
            swap(V, V2);
            gfs(u, v);
            for(int i = 0 ; i < n/2 ; i ++) {
                ans[V[i]] = V2[i];
                ans[V2[i]] = V[i];
            }
            for(int i = 0 ; i < n ; i ++) cout << ans[i]+1 << ' ';
            cout << endl;
            exit(0);
        }
        if (sz[v] <= n/2) {
            good[v] = false;
        } else good[u] = false;
    }
    int root = 0;
    for(int i = 0 ; i < n ; i ++) {
        if (good[i]) {
            root = i;
            break;
        }
    }
    set<pii> st;
    int x = 0;
    for(int neigh: adj[root]) {
        V.clear();
        gfs(neigh, root);
        st.insert({V.size(), x});
        vert[x++] = V;
    }
    pii samp;
    while(st.size() >= 2) {
        auto [sz1, id1] = *st.rbegin();
        st.erase(*st.rbegin());
        auto [sz2, id2] = *st.rbegin();
        st.erase(*st.rbegin());

        ans[vert[id1].back()] = vert[id2].back();
        ans[vert[id2].back()] = vert[id1].back();
        samp = {vert[id1].back(), vert[id2].back()};
        vert[id1].pop_back();
        vert[id2].pop_back();
        if (--sz1 > 0) {
            st.insert({sz1, id1});
        }
        if (--sz2 > 0) {
            st.insert({sz2, id2});
        }
    }
    if (n&1) {
        ans[root] = samp.F;
        ans[samp.S] = root;
    } else {
        auto [_, id] = *st.rbegin();
        ans[root] = vert[id].back();
        ans[vert[id].back()] = root;
    }
    REP(i, n) cout << ans[i]+1 << ' ';
}

int32_t main() {
    
    solve();

    return 0;
}

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