Submission #395376

#	Time	Username	Problem	Language	Result	Execution time	Memory
395376		KoD	Village (BOI20_village)	C++17	75 / 100	170 ms	22720 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) {
                    (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) {
                    (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;
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:118:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |                     (up.size() < N / 2 ? up : down).push_back(u);
      |                      ~~~~~~~~~~^~~~~~~
Village.cpp:130:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  130 |                     (up.size() < (N - 1) / 2 ? up : down).push_back(u);
      |                      ~~~~~~~~~~^~~~~~~~~~~~~

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