Submission #1089980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089980		Mike_Vu	Network (BOI15_net)	C++14	0 / 100	8 ms	15984 KiB

net

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define BITj(x, j) (((x)>>(j))&1)
#define MASK(x) (1LL<<(x))

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 5e5+5;
int n, root;
vector<int> a[maxn];
int node[maxn][2];
vector<pii> edges;

void dfs(int u, int p) {
    if (a[u].size() == 1) {
        node[u][0] = u;
        return;
    }
    for (int v : a[u]) {
        if (v == p) continue;
        dfs(v, u);
        for (int k = 0; k < 2; k++) {
            int nod = node[v][k];
            if (nod == 0) break;
            if (node[u][0] == 0) node[u][0] = nod;
            else if (node[u][1] == 0) node[u][1] = nod;
            else {
                edges.push_back({node[u][1], nod});
                node[u][1] = 0;
            }
        }
    }
    if (p == -1) {
        if (node[u][0] > 0 && node[u][1] > 0) edges.push_back({node[u][0], node[u][1]});
        else edges.push_back({node[u][0], u});
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        a[u].pb(v);
        a[v].pb(u);
    }
    memset(node, 0, sizeof(node));
    for (int i = 1; i <= n; i++) {
        if (a[i].size() > 1) {
            root = i;
            break;
        }
    }
//    cout << root << ' ';
    dfs(root, -1);
    cout << edges.size() << "\n";
    for (pii x : edges) {
        cout << x.fi << ' ' << x.se << "\n";
    }
}

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