Submission #917652

#	Time	Username	Problem	Language	Result	Execution time	Memory
917652		VMaksimoski008	Network (BOI15_net)	C++14	100 / 100	468 ms	41164 KiB

net

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

int n, a, b;
vector<vector<int> > graph;
vector<int> L;

void dfs(int u, int p) {
    for(int &v : graph[u]) {
        if(v == p) continue;
        dfs(v, u);
    }
    if(graph[u].size() == 1) L.push_back(u);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    graph.resize(n+1);

    for(int i=0; i<n-1; i++) {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(1, 0);

    int sz = L.size();
    cout << (sz + 1) / 2 << '\n';
    for(int i=0; i<sz/2; i++)
        cout << L[i] << " " << L[i+sz/2] << '\n';
    if(sz % 2 == 1) cout << L[0] << " " << L.back() << '\n';
    return 0;
}

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