Submission #1306632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306632		pvpro	Village (BOI20_village)	C++20	0 / 100	1 ms	12088 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);
    iota(all(ans1), 0);
    {
        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>> dp(n, vector<int>(2));
        vector<vector<array<int, 3>>> now(n);
        auto fucking_dfs = [&](int v, int prev, auto &&self) -> void {
            int now0 = 0, now1 = 1e9, now2 = 1e9;
            now[v] = {{now0, now1, now2}};
            for (auto &u : graph[v]) {
                if (u == prev) {
                    continue;
                }
                self(u, v, self);
                int now0_, now1_, now2_;
                now0_= min(now0 + dp[u][0], now1 + dp[u][1]);
                now1_= min(now1 + dp[u][0], now0 + dp[u][1]);
                now2_ = min(now2 + dp[u][0], now1 + dp[u][1]);
                now0 = now0_;
                now1 = now1_;
                now2 = now2_;
                now[v].pb({now0, now1, now2});
            }
            if (sz[v] == 1) {
                dp[v][1] = 2;
                dp[v][0] = 1e9;
                return;
            }
            dp[v][0] = min(now1, now2);
            dp[v][1] = min(now0, now1) + 2;
        };
        fucking_dfs(0, 0, fucking_dfs);
        auto answering_dfs = [&](int v, int prev, int res, auto &&self) -> void {
            if (sz[v] == 1) {
                assert(res == 1);
                return;
            }
            int need = -1;
            if (res == 0) {
                if (now[v].back()[2] == dp[v][0]) {
                    need = 2;
                } else {
                    need = 1;
                }
            } else {
                if (now[v].back()[0] + 2 == dp[v][1]) {
                    need = 0;
                } else {
                    need = 1;
                }
            }
            reverse(all(graph[v]));
            int ind = graph[v].size() - 1;
            if (v == 0) {
                ++ind;
            }
            vector<int> vertex;
            for (auto &u : graph[v]) {
                if (u == prev) {
                    continue;
                }
                if (need == 2) {
                    if (now[v][ind - 1][2] + dp[u][0] == now[v][ind][2]) {
                        self(u, v, 0, self);
                    } else {
                        self(u, v, 1, self);
                        vertex.pb(u);
                        need = 1;
                    }
                } else if (need == 0) {
                    if (now[v][ind - 1][0] + dp[u][0] == now[v][ind][0]) {
                        self(u, v, 0, self);
                    } else {
                        self(u, v, 1, self);
                        vertex.pb(u);
                        need = 1;
                    }
                } else {
                    if (now[v][ind - 1][1] + dp[u][0] == now[v][ind][1]) {
                        self(u, v, 0, self);
                    } else {
                        self(u, v, 1, self);
                        vertex.pb(u);
                        need = 0;
                    }
                }
                --ind;
            }
            int lst = -1;
            while (vertex.size() > 1) {
                int a = vertex.back();
                lst = a;
                vertex.pop_back();
                int b = vertex.back();
                vertex.pop_back();
                swap(ans1[a], ans1[b]);
            }
            if (vertex.size() == 1) {
                swap(ans1[vertex.back()], ans1[v]);
            } else if (res == 0) {
                assert(lst != -1);
                swap(ans1[lst], ans1[v]);
            }
        };
        answering_dfs(0, 0, 0, answering_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: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50