Submission #1160694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160694		Ludissey	Network (BOI15_net)	C++20	63 / 100	328 ms	327680 KiB

net

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

vector<int> leefCount;
vector<int> parent;
vector<vector<int>> neigh;
vector<queue<int>> leefs;

int dfs(int x, int p){
    leefCount[x]=(sz(neigh[x])==1);
    parent[x]=p;
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        leefCount[x]+=dfs(u,x);
    }
    return leefCount[x];
}

void addL(int x, int p, int indx){
    if(sz(neigh[x])==1) leefs[indx].push(x);
    for (auto u : neigh[x])
    {
        if(u==p) continue; 
        addL(u,x,indx);
    }
}


int centroid(int x, int p, int tp){
    int tsum=tp;
    int mx=tp;
    int mxI=0;
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        if(leefCount[u]>mx){
            mx=leefCount[u];
            mxI=u;
        }
        tsum+=leefCount[u];
    }
    if(mx*2>tsum) return centroid(mxI,x,tsum-mx);
    return x;
} 

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    neigh.resize(n);
    leefCount.resize(n);
    parent.resize(n);
    for (int i = 0; i < n-1; i++)
    {
        int u,v; cin >> u >> v; u--; v--;
        neigh[u].push_back(v);
        neigh[v].push_back(u);
    }
    int root=0;
    for (int i = 0; i < n; i++)
    {
        if(sz(neigh[i])>1) { root=i; break; }
    }
    dfs(root,-1);
    root=centroid(root,-1,0);
    dfs(root,-1);
    sort(all(neigh[root]), [](int a, int b) {
        return leefCount[a] < leefCount[b];
    });
    leefs.resize(sz(neigh[root]));
    for (int i = 0; i < sz(neigh[root]); i++)
    {
        addL(neigh[root][i],root,i);
    }
    vector<pair<int,int>> ops;
    priority_queue<pair<int,int>> pq;
    for (int i = 0; i < sz(neigh[root]); i++) pq.push({sz(leefs[i]),i});
    while(sz(pq)>1) {
        pair<int,int> u=pq.top(); pq.pop();
        pair<int,int> v=pq.top(); pq.pop();
        ops.push_back({leefs[u.second].front(), leefs[v.second].front()});

        leefs[u.second].pop();
        leefs[v.second].pop();
        u.first--;
        v.first--;
        if(u.first>0) pq.push(u);
        if(v.first>0) pq.push(v);
    }
    if(sz(pq)==1){
        ops.push_back({root,leefs[pq.top().second].front()});
    }
    cout << sz(ops) << "\n";
    for (auto u : ops)
    {
        cout << u.first+1 << " " << u.second+1 << "\n";
    }
    return 0;
}

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