Submission #1000167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000167		y_combinator	Village (BOI20_village)	C++17	100 / 100	43 ms	16720 KiB

Village

#include <algorithm>
#include <ios>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

template <typename F>
class YCombinator {

private:

    const F f = nullptr;

public:

    explicit YCombinator(F&& f) : f(f) {}

    template <typename... Ts>
    decltype(auto) operator()(Ts&&... arguments) const {

        return f(*this, std::forward<Ts>(arguments)...);

    }

};

template <typename F>
YCombinator(F) -> YCombinator<F>;

auto solve() {

    auto n = 0;

    std::cin >> n;

    auto adj = std::vector<std::vector<int>>(n);

    for (auto i = 0; i < n - 1; ++i) {
        auto a = 0;
        auto b = 0;
        std::cin >> a >> b;
        --a;
        --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    auto idxs = std::vector<int>(n);
    auto mn_len = 0;
    auto mx_len = 0ll;
    auto order = std::vector<int>();
    auto szs = std::vector<int>(n, 1);
    auto v = std::vector<int>(n);

    order.reserve(n);

    std::iota(std::begin(v), std::end(v), 0);

    YCombinator(
        [&](auto self, int node, int par) -> void {
            order.push_back(node);
            for (auto x : adj[node]) {
                if (x != par) {
                    self(x, node);
                    mx_len += std::min(szs[x], n - szs[x]) * 2;
                    szs[node] += szs[x];
                }
            }
            if (v[node] == node) {
                std::swap(v[node], v[par != -1 ? par : adj[node][0]]);
                mn_len += 2;
            }
        }
    )(0, -1);

    std::cout << mn_len << ' ' << mx_len << '\n';

    for (auto i = 0; i < n; ++i) {
        std::cout << v[i] + 1 << (i < n - 1 ? ' ' : '\n');
        idxs[order[i]] = i;
    }

    for (auto i = 0; i < n; ++i) {
        std::cout << order[(idxs[i] + n / 2) % n] + 1 << (i < n - 1 ? ' ' : '\n');
    }

}

auto main() -> int {

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    solve();

    return 0;

}

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