Submission #932994

#	Time	Username	Problem	Language	Result	Execution time	Memory
932994		ArashJafariyan	Network (BOI15_net)	C++17	100 / 100	340 ms	38504 KiB

net

#include <bits/stdc++.h>

#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) 0
#endif

typedef long long ll;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

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

    int n;
    std::cin >> n;

    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int v, u;
        std::cin >> v >> u;
        v--; u--;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    std::vector<int> leaf;
    auto dfs = [&](auto self, int v, int p) -> void {
        if (adj[v].size() == 1) {
            leaf.push_back(v);
        }
        for (int u : adj[v]) {
            if (u != p) {
                self(self, u, v);
            }
        }
    };
    dfs(dfs, 0, 0);

    int sz = leaf.size();
    std::cout << (sz + 1) / 2 << '\n';
    for (int i = 0; i + sz / 2 < sz; i++) {
        std::cout << leaf[i] + 1 << ' ' << leaf[i + sz / 2] + 1 << '\n';
    }

    return 0;
}

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