Submission #563735

#	Time	Username	Problem	Language	Result	Execution time	Memory
563735		KoD	Network (BOI15_net)	C++17	100 / 100	546 ms	48868 KiB

net

#include <bits/stdc++.h>

using ll = long long;

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class T> constexpr T infty = std::numeric_limits<T>::max() / 2;

template <class F> struct rec_lambda : private F {
    explicit rec_lambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<vector<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);
    }
    vector<int> size(N);
    rec_lambda([&](auto&& dfs, const int u, const int p) -> void {
        size[u] = (int)graph[u].size();
        for (const int v : graph[u]) {
            if (v != p) {
                dfs(v, u);
                size[u] += size[v];
            }
        }
    })(0, -1);
    const int L = size[0];
    const int centroid = [&] {
        int u = 0, p = -1;
        while (true) {
            bool found = false;
            for (const int v : graph[u]) {
                if (v != p and size[v] > L / 2) {
                    p = u;
                    u = v;
                    found = true;
                    break;
                }
            }
            if (!found) {
                break;
            }
        }
        return u;
    }();
    vector<int> list;
    for (const int root : graph[centroid]) {
        rec_lambda([&](auto&& dfs, const int u, const int p) -> void {
            if (graph[u].size() == 1) {
                list.push_back(u);
            }
            for (const int v : graph[u]) {
                if (v != p) {
                    dfs(v, u);
                }
            }
        })(root, centroid);
    }
    if (list.size() % 2 == 1) {
        list.push_back(centroid);
    }
    const int H = list.size() / 2;
    std::cout << H << '\n';
    for (int i = 0; i < H; ++i) {
        std::cout << list[i] + 1 << ' ' << list[i + H] + 1 << '\n';
    }
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37