Submission #1280713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280713		Blistering_Barnacles	Village (BOI20_village)	C++20	0 / 100	1 ms	12088 KiB

Village

//Billions of bilious blue blistering barnacles in a thundering typhoon!
//Yesterday is history, tomorrow is a mystery, today is a gift of God, which is why we call it the present.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    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].push_back(v), adj[v].push_back(u);
    }
    vector<int> sz(n + 1);
    auto dfs = [&](auto &&self, int v, int par) -> void {
        sz[v] = 1;
        for (int u: adj[v]) {
            if (u == par) continue;
            self(self, u, v);
            sz[v] += sz[u];
        }
    };
    dfs(dfs, 1, 0);
    auto get = [&](auto &&self, int v, int par) -> int {
        for (int u: adj[v]) {
            if (u == par || sz[u] <= n / 2) continue;
            return self(self, u, v);
        }
        return v;
    };
    int cen = get(get, 1, 0);
    vector<vector<pair<int, int>>> vals(n + 1);
    for (int u: adj[cen]) {
        auto dfs2 = [&](auto &&self, int v, int par, int d) -> void {
            vals[u].push_back({d, v});
            for (int u2: adj[v]) {
                if (u2 == par) continue;
                self(self, u2, v, d + 1);
            }
        };
        dfs2(dfs2, u, cen, 1);
    }
    set<tuple<int, int, int>> se;
    vector<int> ptr(n + 1);
    for (int u: adj[cen]) {
        sort(vals[u].rbegin(), vals[u].rend());
        se.insert({vals[u][0].first, vals[u][0].second, u});
    }
    vector<int> ans(n + 1);
    cout << cen << "\n";
    i64 sum = 0;
    for (int i = 2; i <= n; i++) {
        sum += 2 * min(sz[i], n - sz[i]);
    }
    int lst = 0;
    while ((int)se.size() > 1) {
        auto [d1, v1, u1] = *se.rbegin();
        se.erase(--se.end());
        auto [d2, v2, u2] = *se.rbegin();
        se.erase(--se.end());
        lst = v1;
        ans[v1] = v2, ans[v2] = v1;
        ptr[u1]++;
        ptr[u2]++;
        if (ptr[u1] < (int)vals[u1].size()) se.insert({vals[u1][ptr[u1]].first, vals[u1][ptr[u1]].second, u1});
        if (ptr[u2] < (int)vals[u2].size()) se.insert({vals[u2][ptr[u2]].first, vals[u2][ptr[u2]].second, u2});
    }
    if ((int) se.size() == 1) {
        auto [d1, v1, u1] = *se.begin();
        ans[v1] = cen, ans[cen] = v1;
    } else {
        ans[cen] = ans[lst], ans[lst] = cen;
    }
    cout << sum << "\n";
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << "\n";
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

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