Submission #698363

#	Time	Username	Problem	Language	Result	Execution time	Memory
698363		_martynas	Network (BOI15_net)	C++11	100 / 100	728 ms	77096 KiB

net

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB push_back

using pii = pair<int, int>;
using vi = vector<int>;

const int MXN = 5e5+5;

int n;
vi adj[MXN];
int leaf_cnt[MXN];
int root;
vector<vi> leaves;

void dfs1(int u, int p) {
    leaf_cnt[u] = adj[u].size() == 1;
    for(int v : adj[u]) {
        if(v == p) continue;
        dfs1(v, u);
        leaf_cnt[u] += leaf_cnt[v];
    }
}

int dfs2(int u, int p) {
    for(int v : adj[u]) {
        if(v == p) continue;
        if(leaf_cnt[v] > (leaf_cnt[root]+1)/2) {
            return dfs2(v, u);
        }
    }
    return u;
}

void dfs3(int u, int p, vi &l) {
    if(adj[u].size() == 1) l.PB(u);
    for(int v : adj[u]) {
        if(v == p) continue;
        dfs3(v, u, l);
    }
}

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

    cin >> n;
    for(int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b;
        adj[a].PB(b);
        adj[b].PB(a);
    }

    for(int i = 1; i <= n; i++) {
        if(adj[i].size() > 1) {
            root = i;
            dfs1(i, -1);
            break;
        }
    }
    root = dfs2(root, -1);
    for(int u : adj[root]) {
        vi l;
        dfs3(u, root, l);
        leaves.PB(l);
    }

    priority_queue<pii> PQ;
    for(int i = 0; i < leaves.size(); i++) {
        PQ.push({leaves[i].size(), i});
    }
    vector<pii> ans;
    while(!PQ.empty()) {
        if(PQ.size() == 1) {
            auto p = PQ.top();
            PQ.pop();
            ans.PB({leaves[p.S].back(), root});
        }
        else {
            auto p_a = PQ.top(); PQ.pop();
            auto p_b = PQ.top(); PQ.pop();
            ans.PB({leaves[p_a.S].back(), leaves[p_b.S].back()});
            leaves[p_a.S].pop_back(), leaves[p_b.S].pop_back();
            p_a.F--, p_b.F--;
            if(p_a.F) PQ.push(p_a);
            if(p_b.F) PQ.push(p_b);
        }
    }
    cout << ans.size() << "\n";
    for(auto p : ans) cout << p.F << " " << p.S << "\n";
    return 0;
}
/*
6
1 2
2 3
2 4
5 4
6 4

8
1 2
2 3
3 4
4 5
3 6
3 7
3 8



*/

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i = 0; i < leaves.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~

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