Submission #917659

#	Time	Username	Problem	Language	Result	Execution time	Memory
917659		VMaksimoski008	Network (BOI15_net)	C++14	100 / 100	637 ms	45664 KiB

net

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

int n, a, b, i;
vector<int> L, G[500005];

void dfs(int u, int p) {
    for(int &v : G[u]) if(v != p) dfs(v, u);
    if(G[u].size() == 1) L.pb(u);
}

int main() {
    cin >> n;

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

    dfs(1, 0);

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

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