Submission #95951

#	Time	Username	Problem	Language	Result	Execution time	Memory
95951		caesar2001	Network (BOI15_net)	C++14	100 / 100	909 ms	90220 KiB

net

#include <bits/stdc++.h>
#define ll long long
#define lsb(x) (x & -x)

using namespace std;

void dfs(int node, vector<int> &dad, const vector<vector<int>> &g, vector<int> &leaves) {
    bool flag = 0;
    for(auto it : g[node]) {
        if(it != dad[node]) {
            dad[it] = node;
            dfs(it, dad, g, leaves);

            leaves[node] += leaves[it];
            flag = 1;
        }
    }

    if(!flag)
        leaves[node] = 1;
}

void getleaves(int node, int dad, const vector<vector<int>> &g, vector<int> &v) {
    bool flag = 0;
    for(auto it : g[node]) {
        if(it == dad)
            continue;

        getleaves(it, node, g, v);
        flag = 1;
    }

    if(!flag)
        v.push_back(node);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);

    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    int start = 1;
    for(int i = 1; i < n; i ++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 1; i <= n; i ++)
        if(g[i].size() > 1)
            start = i;

    vector<int> leaves(n + 1, 0);
    vector<int> dad(n + 1, 0);
    dfs(start, dad, g, leaves);

    int centroid = 0;
    for(int i = 1; i <= n; i ++) {
        int lim = leaves[start] / 2;
        bool isok = 1;
        for(auto it : g[i]) {
            if(dad[i] == it && leaves[start] - leaves[i] > lim)
                isok = 0;
            else if(dad[i] != it && leaves[it] > lim)
                isok = 0;
        }

        if(isok && g[i].size() > 1) /// a doua conditie de aici???
            centroid = i;
    }
    assert(centroid != 0);

    priority_queue<pair<int, int>> pq;
    vector<vector<int>> listofleaves(n + 1);
    for(auto it : g[centroid]) {
        getleaves(it, centroid, g, listofleaves[it]);
        pq.push({listofleaves[it].size(), it});
    }

    vector<pair<int, int>> sol;
    while(pq.size() >= 2) {
        auto a = pq.top().second;
        pq.pop();
        auto b = pq.top().second;
        pq.pop();

        sol.push_back({listofleaves[a].back(), listofleaves[b].back()}); /// to change
        listofleaves[a].pop_back();
        listofleaves[b].pop_back();

        if(listofleaves[a].size() > 0)
            pq.push({listofleaves[a].size(), a});
        if(listofleaves[b].size() > 0)
            pq.push({listofleaves[b].size(), b});
    }

    if(pq.size() == 1)
        sol.push_back({centroid, listofleaves[pq.top().second].back()});

    cout << sol.size() << "\n";
    for(auto it : sol)
       cout << it.first << " " << it.second << "\n";

    return 0;
}

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