Submission #911479

#	Time	Username	Problem	Language	Result	Execution time	Memory
911479		12345678	Network (BOI15_net)	C++17	0 / 100	7 ms	25180 KiB

net

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;
int n, u, v, st, sz[nx], c, res;
vector<int> d[nx], l[nx];
priority_queue<pair<int, int>> pq;

int dfssz(int u, int p)
{
    sz[u]=(d[u].size()==1);
    for (auto v:d[u]) if (v!=p) sz[u]+=dfssz(v, u);
    return sz[u];
}

int findcentroid(int u, int p, int rtsz)
{
    for (auto v:d[u]) if (v!=p&&sz[v]*2>rtsz) return findcentroid(v, u, rtsz);
    return u;
}

void dfsadd(int u, int p, vector<int> &x)
{
    if (d[u].size()==1) x.push_back(u);
    for (auto v:d[u]) if (v!=p) dfsadd(v, u, x); 
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=0; i<n-1; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    for (int i=0; i<n; i++) if (d[i].size()>1) st=i;
    c=findcentroid(st, st, dfssz(st, st));
    for (auto v:d[c]) dfsadd(v, c, l[v]);
    for (auto v:d[c]) pq.push({l[v].size(), v});
    cout<<(n+1)/2<<'\n';
    while (!pq.empty())
    {
        if (pq.size()>1)
        {
            auto f=pq.top().second;
            pq.pop();
            auto s=pq.top().second;
            pq.pop();
            cout<<l[f][l[f].size()-1]<<' '<<l[s][l[s].size()-1]<<'\n';
            l[f].pop_back(); l[s].pop_back();
            if (!l[f].empty()) pq.push({l[f].size(), f});
            if (!l[s].empty()) pq.push({l[s].size(), s});
        }
        else 
        {
            auto f=pq.top().second;
            cout<<1+(l[f][0]==1)<<' '<<l[f][0]<<'\n';
            pq.pop();
        }
    }

}

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