Submission #113175

#	Time	Username	Problem	Language	Result	Execution time	Memory
113175		rkocharyan	Network (BOI15_net)	C++14	100 / 100	632 ms	49956 KiB

net

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 7;

vector <int> g[N];
vector <int> l;
int tin[N];
int timer;

void dfs(int v, int pr) {
    tin[v] = timer++;
    if (g[v].size() == 1) {
        l.push_back(v);
    }
    for (int to : g[v]) {
        if (to != pr) {
            dfs(to, v);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0, -1);
    sort(l.begin(), l.end(), [&] (int a, int b) {
        return tin[a] < tin[b];
    });
    int k = (int) l.size();
    int m = k / 2;
    cout << (k + 1) / 2 << '\n';
    for (int i = 0; i < (k + 1) / 2; i++) {
        cout << l[i] + 1 << ' ' << l[(i + m) % k] + 1 << '\n';
    }
    return 0;
}

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