Submission #1186889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186889		Joo	Network (BOI15_net)	C++20	0 / 100	6 ms	12104 KiB

net

#include <bits/stdc++.h>
using namespace std;

const int MXN = 5e5 + 10;

vector<int> G[MXN];
vector<pair<int, int>> deg_one;
int dep[MXN];

void dfs(int u, int p) {
    for (int v : G[u]) {
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }

    if (G[u].size() == 1) {
        deg_one.emplace_back(dep[u], u);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    dfs(1, -1);

    sort(deg_one.begin(), deg_one.end());
    int l = 0, r = (int)deg_one.size() - 1;
    vector<pair<int, int>> ans;
    for (; l < r; l++, r--) {
        auto [dep_u, u] = deg_one[l];
        auto [dep_v, v] = deg_one[r];
        ans.emplace_back(u, v);
    }

    if (l == r) {
        ans.emplace_back(1, deg_one[l].second);
    }

    cout << ans.size() << "\n";
    for (auto [u, v] : ans) {
        cout << u << " " << v << "\n";
    }
}

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