Submission #1306615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306615		pvpro	Village (BOI20_village)	C++20	50 / 100	119 ms	37760 KiB

Village

#ifndef LOCAL
#pragma GCC Optimize("O3,Ofast,unroll-loops")
#pragma GCC Target("bmi,bmi2,avx,avx2")
#endif
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define int ll

#define f first 
#define s second 
#define mp make_pair 
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin() (x).rend()
#ifndef LOCAL
#define endl "\n"
#endif

mt19937 rnd(11);

const int LOG_N = 20;

vector<vector<int>> graph;
vector<int> tin, tout, high, sz;
vector<int> binup[LOG_N];

int Tm = 0;

void calc(int v, int h, int prev = 0) {
    sz[v] = 1;
    high[v] = h++;
    binup[0][v] = prev;
    tin[v] = Tm++;
    for (auto &u : graph[v]) {
        if (u != prev) {
            calc(u, h, v);
            sz[v] += sz[u];
        }
    }
    tout[v] = Tm;
}

int find_center(int v, int prev = -1) {
    for (auto &u : graph[v]) {
        if (u != prev && sz[u] * 2 >= sz[0]) {
            return find_center(u, v);
        }
    }
    return v;
}

bool inside(int a, int b) {
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int lca(int a, int b) {
    if (inside(a, b)) {
        return a;
    }
    for (int l = LOG_N - 1; l >= 0; --l) {
        if (!inside(binup[l][a], b)) {
            a = binup[l][a];
        }
    }
    return binup[0][a];
}

int dist(int a, int b) {
    int c = lca(a, b);
    return high[a] + high[b] - high[c] * 2;
}

void solve() {
    int n;
    cin >> n;
    tin.resize(n);
    tout.resize(n);
    high.resize(n);
    sz.resize(n);
    binup[0].resize(n);
    graph.resize(n);
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    calc(0, 0);
    for (int l = 1; l < LOG_N; ++l) {
        binup[l].resize(n);
        for (int i = 0; i < n; ++i) {
            binup[l][i] = binup[l - 1][binup[l - 1][i]];
        }
    }
    vector<int> ans1(n), ans2(n);
    {
        int center = find_center(0);
        vector<vector<int>> vertex;
        auto dfs = [&](int v, int prev, auto &&self) -> void {
            vertex.back().pb(v);
            for (auto &u : graph[v]) {
                if (u != prev) {
                    self(u, v, self);
                }
            }
        };
        for (auto &u : graph[center]) {
            vertex.pb({});
            dfs(u, center, dfs);
        }
        if (n % 2 == 0) {
            vertex.pb({center});
        }
        priority_queue<pii> q;
        for (int i = 0; i < vertex.size(); ++i) {
            q.push(mp(vertex[i].size(), i));
        }
        int lst;
        while (!q.empty()) {
            int a = q.top().s;
            q.pop();
            int b = q.top().s;
            q.pop();
            lst = vertex[a].back();
            ans2[vertex[a].back()] = vertex[b].back();
            ans2[vertex[b].back()] = vertex[a].back();
            vertex[a].pop_back();
            vertex[b].pop_back();
            if (!vertex[a].empty()) {
                q.push(mp(vertex[a].size(), a));
            }
            if (!vertex[b].empty()) {
                q.push(mp(vertex[b].size(), b));
            }
        }
        if (n % 2 == 1) {
            swap(ans2[lst], ans2[center]);
            ans2[lst] = center;
        }
    }
    {
        vector<vector<int>> toMerge(n);
        auto fucking_dfs = [&](int v, int prev, auto &&self) -> void {
            for (auto &u : graph[v]) {
                if (u == prev) {
                    continue;
                }
                self(u, v, self);
            }
            while (toMerge[v].size() >= 2) {
                int a = toMerge[v].back();
                toMerge[v].pop_back();
                int b = toMerge[v].back();
                toMerge[v].pop_back();
                ans1[a] = b;
                ans1[b] = a;
            }
            if (toMerge[v].size()) {
                ans1[toMerge[v].back()] = v;
                ans1[v] = toMerge[v].back();
            } else {
                if (v == 0) {
                    swap(ans1[graph[v][0]], ans1[v]);
                    ans1[graph[v][0]] = 0;
                } else {
                    toMerge[prev].pb(v);
                }
            }
        };
        fucking_dfs(0, 0, fucking_dfs);
    }
    int answer1 = 0, answer2 = 0;
    for (int i = 0; i < n; ++i) {
        answer1 += dist(i, ans1[i]);
        answer2 += dist(i, ans2[i]);
    }
    cout << answer1 << ' ' << answer2 << endl;
    for (auto &x : ans1) {
        cout << x+1 << ' ';
    }
    cout << endl;
    for (auto &x : ans2) {
        cout << x+1 << ' ';
    }
    cout << endl;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else
        ios::sync_with_stdio(false);
        cin.tie(0);
    #endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50