Submission #930083

#	Time	Username	Problem	Language	Result	Execution time	Memory
930083		Karoot	Network (BOI15_net)	C++17	100 / 100	744 ms	128828 KiB

net

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <deque>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

const int MAXN = 5e5+1;
vector<int> adj[MAXN];
vector<pair<int, int> > children[MAXN];
bool isLeaf[MAXN];
int leafSz[MAXN];
double leafCount = 0;
bool skip[MAXN];

int rootTree(int node, int parent){
    leafSz[node] = 0;
    if (adj[node].size() == 1 && node != parent){
        leafCount++;
        leafSz[node]++;
        isLeaf[node] = true;
        if (node != parent)children[parent].push_back({leafSz[node], node});
        return leafSz[node];
    }
    for (auto e : adj[node]){
        if (e != parent)leafSz[node] += rootTree(e, node);
    }
    if (node != parent)children[parent].push_back({leafSz[node], node});
    return leafSz[node];
}

int getCentroid(int node){
    if ((double)children[node][0].first <= (leafCount/2.0)){
        return node;
    }

    return getCentroid(children[node][0].second);
}

vector<int> tempLeaves;

void getLeaves(int node){
    if (isLeaf[node])tempLeaves.push_back(node);
    for (auto p : children[node]){
        getLeaves(p.second);
    }
}

set<int> leaves[MAXN];

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

    rootTree(0, 0);

    for (int i = 0; i < n; i++)sort(rall(children[i]));
    int nRoot = getCentroid(0);

    for (int i = 0; i < n; i++){
        children[i].clear();
        leafSz[i] = 0;
    }

    rootTree(nRoot, nRoot);


    sort(rall(children[nRoot]));

    int firstOne = -1;

    vector<pair<int, int> > ans;

    set<pair<int, int> > s;

    for (auto p : children[nRoot]){
        tempLeaves.clear();
        getLeaves(p.second);
        for (int x : tempLeaves)leaves[p.second].insert(x);
        s.insert(p);
    }

    int counter = 0;
    while (s.size()){
        //cout << ++counter << endl;
        auto it = s.end();
        it--;
        pair<int, int> p1 = *it;
        if (s.size() == 1){
            for (auto& e : leaves[p1.second]){
                ans.push_back({firstOne, e});
            }
            break;
        }
        it--;
        pair<int, int> p2 = *it;

        //cout << "(" << p1.first << "," << p1.second << ")   " << "(" << p2.first << "," << p2.second << ")  " << endl;

        ans.push_back({*leaves[p1.second].begin(), *leaves[p2.second].begin()});

        if (firstOne == -1)firstOne = *leaves[p1.second].begin();

        leaves[p1.second].erase(leaves[p1.second].begin());
        leaves[p2.second].erase(leaves[p2.second].begin());

        auto itr = s.end();
        itr--;
        s.erase(itr);
        itr = s.end();
        itr--;
        s.erase(itr);
        if (leaves[p1.second].size())s.insert({leaves[p1.second].size(), p1.second});
        if (leaves[p2.second].size())s.insert({leaves[p2.second].size(), p2.second});


    }


    cout << ans.size() << endl;
    for (auto p : ans)cout << p.first+1 << " " << p.second+1 << endl;









    



    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:110:9: warning: unused variable 'counter' [-Wunused-variable]
  110 |     int counter = 0;
      |         ^~~~~~~

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