Submission #340190

#	Time	Username	Problem	Language	Result	Execution time	Memory
340190		blue	Network (BOI15_net)	C++11	100 / 100	940 ms	50028 KiB

net

#include <iostream>
#include <queue>
using namespace std;

int n;
vector<int> edge[500001];
vector<int> edge_size(500001, 0);
vector<int> p(500001, 0);
vector<int> dfs_leaf;

void dfs(int u)
{
    if(edge[u].size() == 1) dfs_leaf.push_back(u);
    for(int v: edge[u])
    {
        if(p[u] == v) continue;
        dfs(v);
    }
}

int main()
{
    cin >> n;
    int a, b;
    for(int i = 1; i <= n-1; i++)
    {
        cin >> a >> b;
        edge[a].push_back(b);
        edge_size[a]++;
        edge[b].push_back(a);
        edge_size[b]++;
    }

    queue<int> tbv;
    for(int i = 1; i <= n; i++) if(edge_size[i] == 1) tbv.push(i);
    while(!tbv.empty())
    {
        a = tbv.front();
        tbv.pop();

        for(int v: edge[a])
        {
            if(p[v] == a) continue;
            p[a] = v;
            edge_size[v]--;
            if(edge_size[v] == 1) tbv.push(v);
        }
    }

    int root = a;
    dfs(root);

    int s = dfs_leaf.size();

    if(s % 2 == 0)
    {
        cout << s/2 << '\n';
        for(int i = 0; i < s/2; i++) cout << dfs_leaf[i] << ' ' << dfs_leaf[s/2 + i] << '\n';
    }
    else
    {
        s--;
        cout << s/2 + 1 << '\n';
        for(int i = 0; i < s/2; i++) cout << dfs_leaf[i] << ' ' << dfs_leaf[s/2 + i] << '\n';
        cout << dfs_leaf[0] << ' ' << dfs_leaf[s] << '\n';
    }
}

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