Submission #751168

#	Time	Username	Problem	Language	Result	Execution time	Memory
751168		ljuba	Network (BOI15_net)	C++17	100 / 100	495 ms	47664 KiB

net

#include <bits/stdc++.h>

using namespace std;

const int mxN = 5e5 + 12;
vector<int> adj[mxN];

vector<int> lisce;

void dfs(int s, int p = -1) {
    if(adj[s].size() == 1) lisce.push_back(s);
    for(auto e : adj[s]) {
        if(e == p) continue;
        dfs(e, s);
    }
}

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

    int n;
    cin >> n;

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

    dfs(0);

    int vel = lisce.size();
    cout << (vel + 1) / 2 << '\n';

    for(int i = 0; i < (vel + 1) / 2; ++i) {
        int x = lisce[i];
        int y = lisce[(i + vel / 2) % vel];
        cout << x + 1 << " " << y + 1 << '\n';
    }
}

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