제출 #395379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395379		KoD	Village (BOI20_village)	C++17	50 / 100	155 ms	21764 KiB

Village

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

int main() {
    int N;
    std::cin >> N;
    Vec<Vec<int>> graph(N);
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        std::cin >> a >> b;
        a -= 1;
        b -= 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    int min = -1, max = -1;
    Vec<int> min_v(N), max_v(N);
    // minimum
    {
        Vec<std::pair<int, int>> use;
        auto dfs = [&](auto&& dfs, const int u, const int p) -> bool {
            int child = -1;
            bool done = false;
            for (const int v: graph[u]) {
                if (v != p) {
                    if (dfs(dfs, v, u)) {
                        done = true;
                    }
                    child = v;
                }
            }
            if (!done) {
                if (p == -1) {
                    use.emplace_back(u, child);
                    return false;
                }
                use.emplace_back(u, p);
                return true;
            }
            return false;
        };
        dfs(dfs, 0, -1);
        min = 2 * (int) use.size();
        Vec<Vec<int>> tree(N);
        for (const auto [u, v]: use) {
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        Vec<bool> done(N);
        Vec<int> order;
        auto build = [&](auto&& build, const int u, const int p) -> void {
            done[u] = true;
            order.push_back(u);
            for (const auto v: tree[u]) {
                if (v != p) {
                    build(build, v, u);
                }
            }
        };
        for (int r = 0; r < N; ++r) {
            if (!done[r]) {
                build(build, r, -1);
                const auto len = (int) order.size();
                for (int i = 0; i < len; ++i) {
                    min_v[order[i]] = order[(i + 1) % len];
                }
                order.clear();
            }
        }
    }
    // maximum
    {
        max = 0;
        // Vec<int> subtree(N);
        // auto setup = [&](auto&& setup, const int u, const int p) -> void {
        //     subtree[u] = 1;
        //     for (const auto v: graph[u]) {
        //         if (v != p) {
        //             setup(setup, v, u);
        //             subtree[u] += subtree[v];
        //         }
        //     }
        //     if (p != -1) {
        //         max += 2 * std::min(subtree[u], N - subtree[u]);
        //     }
        // };
        // setup(setup, 0, -1);
        // auto find = [&](auto&& find, const int u, const int p) -> int {
        //     for (const auto v: graph[u]) {
        //         if (v != p and subtree[v] * 2 > N) {
        //             return find(find, v, u);
        //         }
        //     }
        //     return u;
        // };
        // const auto cent = find(find, 0, -1);
        // Vec<Vec<int>> group;
        // auto listup = [&](auto&& listup, const int u, const int p) -> void {
        //     group.back().push_back(u);
        //     for (const auto v: graph[u]) {
        //         if (v != p) {
        //             listup(listup, v, u);
        //         }
        //     }
        // };
        // for (const auto u: graph[cent]) {
        //     group.push_back({});
        //     listup(listup, u, cent);
        // }
        // if (N % 2 == 0) {
        //     group.push_back({});
        //     group.back().push_back(cent);
        //     Vec<int> up, down;
        //     for (const auto& g: group) {
        //         for (const auto u: g) {
        //             ((int) up.size() < N / 2 ? up : down).push_back(u);
        //         }
        //     }
        //     for (int i = 0; i < N / 2; ++i) {
        //         max_v[up[i]] = down[i];
        //         max_v[down[i]] = up[i];
        //     }
        // }
        // else {
        //     Vec<int> up, down;
        //     for (const auto& g: group) {
        //         for (const auto u: g) {
        //             ((int) up.size() < (N - 1) / 2 ? up : down).push_back(u);
        //         }
        //     }
        //     for (int i = 0; i < (N - 1) / 2; ++i) {
        //         max_v[up[i]] = down[i];
        //         max_v[down[i]] = up[i];
        //     }            
        //     max_v[up[0]] = cent;
        //     max_v[cent] = down[0];
        // }
    }
    std::cout << min << ' ' << max << '\n';
    for (int i = 0; i < N; ++i) {
        std::cout << min_v[i] + 1 << " \n"[i + 1 == N];
    }
    for (int i = 0; i < N; ++i) {
        std::cout << max_v[i] + 1 << " \n"[i + 1 == N];
    }
    return 0;
}

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