Submission #410597

#	Time	Username	Problem	Language	Result	Execution time	Memory
410597		iulia13	Network (BOI15_net)	C++14	100 / 100	1012 ms	47640 KiB

net

#include <iostream>
#include <vector>
using namespace std;
const int N = 500005;
vector <int> g[N];
int nr = 0;
vector <int> v;
void dfs(int nod, int dad = 0)
{
    if (g[nod].size() == 1)
        v.push_back(nod);
    for (auto x : g[nod])
        if (x != dad)
            dfs(x, nod);
}
int main()
{
    int n, i, a, b;
    cin >> n;
    for (i = 1; i < n; i++)
    {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1);
    nr = v.size();
    int ans = (nr + 1) / 2;
    cout << ans;
    for (i = 0; i < nr / 2; i ++)
        cout << endl << v[i] << " " << v[i + ans];
    if (nr % 2)
        cout << endl << v[nr / 2] << " " << v[0];
    return 0;
}

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