Submission #729500

#	Time	Username	Problem	Language	Result	Execution time	Memory
729500		Tigerpants	Network (BOI15_net)	C++17	100 / 100	521 ms	70252 KiB

net

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <map>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define sz(a) a.size()
#define pb(a) push_back(a)

ll N;

vvll g;

ll root;

vpll edges;

vll dp_dfs(ll cur, ll par) {
    vll res;
    bool is_leaf = true;
    for (vll::iterator itr = g[cur].begin(); itr != g[cur].end(); itr++) {
        if (*itr == par) continue;
        is_leaf = false;
        vll child = dp_dfs(*itr, cur);
        for (vll::iterator t = child.begin(); t != child.end(); t++) res.pb(*t);
        if (sz(res) >= 3) {
            ll a = res.back(); res.pop_back();
            ll b = res.front(); res.erase(res.begin());
            edges.pb(mp(a, b));
        }
    }
    if (is_leaf) {
        res.pb(cur);
    }
    return res;
} 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    g.resize(N);
    rep(i, 0, N - 1) {
        ll tmpa, tmpb;
        cin >> tmpa >> tmpb;
        tmpa--; tmpb--;
        g[tmpa].pb(tmpb);
        g[tmpb].pb(tmpa);
    }

    root = 0;
    while (sz(g[root]) == 1) root++;

    vll res = dp_dfs(root, -1);
    if (sz(res) == 1) {
        edges.pb(mp(res[0], root));
    } else {
        edges.pb(mp(res[0], res[1]));
    }

    cout << sz(edges) << "\n";
    for (vpll::iterator itr = edges.begin(); itr != edges.end(); itr++) {
        cout << itr->first + 1 << " " << itr->second + 1 << "\n";
    }
    cout << flush;

    return 0;
}

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