Submission #1280072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280072		MisterReaper	Village (BOI20_village)	C++20	50 / 100	57 ms	28020 KiB

Village

// File village.cpp created on 16.10.2025 at 20:35:16
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(1E5) + 5;

int N;
std::vector<int> adj[max_N];

i64 ans1 = 0;
int go[max_N];
int ord1[max_N];

void dfs1(int v, int pr) {
    for (auto u : adj[v]) {
        if (u == pr) {
            continue;
        }
        dfs1(u, v);
        if (go[u] == u) {
            std::swap(go[u], go[v]);
            ans1 += 2;
        }
    }
    if (pr == -1 && go[v] == v) {
        std::swap(go[v], go[adj[v][0]]);
        ans1 += 2;
    }
}

int siz[max_N];

void dfs2(int v, int pr) {
    siz[v] = 1;
    for (auto u : adj[v]) {
        if (u == pr) {
            continue;
        }
        dfs2(u, v);
        siz[v] += siz[u];
    }
}

int tord[max_N];
int ord2[max_N];
int tim = 0;

void dfs3(int v, int pr) {
    tord[tim++] = v;
    for (auto u : adj[v]) {
        if (u == pr) {
            continue;
        }
        dfs3(u, v);
    }
}

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

    std::cin >> N;

    for (int i = 1; i < N; ++i) {
        int A, B;
        std::cin >> A >> B;
        --A, --B;
        adj[A].emplace_back(B);
        adj[B].emplace_back(A);
    }

    for (int i = 0; i < N; ++i) {
        go[i] = i;
    }
    dfs1(0, -1);

    for (int i = 0; i < N; ++i) {
        ord1[i] = go[i];
    }

    dfs2(0, -1);

    i64 ans2 = 0;
    for (int i = 1; i < N; ++i) {
        ans2 += std::min(siz[i], N - siz[i]) * 2;
    }

    int centro = 0;
    while (true) {
        int ncentro = -1;
        for (auto u : adj[centro]) {
            if (siz[u] > siz[centro]) {
                continue;
            }
            if (siz[u] * 2 > N) {
                ncentro = u;
                break;
            }
        }
        if (ncentro == -1) {
            break;
        }
        centro = ncentro;
    }

    dfs3(centro, -1);

    for (int i = 0; i < N; ++i) {
        ord2[i] = tord[(i + N / 2) % N];
    }

    std::cout << ans1 << ' ' << ans2 << '\n';
    for (int i = 0; i < N; ++i) {
        std::cout << ord1[i] + 1 << " \n"[i == N - 1];
    }
    for (int i = 0; i < N; ++i) {
        std::cout << ord2[i] + 1 << " \n"[i == N - 1];
    }

    return 0;
}

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