Submission #923565

#	Time	Username	Problem	Language	Result	Execution time	Memory
923565		andrei_iorgulescu	Network (BOI15_net)	C++14	100 / 100	666 ms	120444 KiB

net

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
int deg[500005];
vector<int>g[500005];
int nrf[500005],heavyson[500005],mxf[500005];
int frunze;
vector<int>l[500005],f[500005];
 
void dfs(int nod,int tata)
{
    if (deg[nod] == 1)
        nrf[nod] = 1;
    else
    {
        for (auto vecin : g[nod])
        {
            if (vecin != tata)
            {
                dfs(vecin,nod);
                nrf[nod] += nrf[vecin];
                if (nrf[vecin] > mxf[nod])
                {
                    mxf[nod] = nrf[vecin];
                    heavyson[nod] = vecin;
                }
            }
        }
    }
}
 
int findroot(int nod)
{
    if (mxf[nod] <= frunze / 2 + frunze % 2)
        return nod;
    else
        return findroot(heavyson[nod]);
}
 
vector<pair<int,int>>sol;
 
void dfs2(int nod,int tata)
{
    for (auto vecin : g[nod])
    {
        if (vecin != tata)
        {
            f[nod].push_back(vecin);
            dfs2(vecin,nod);
        }
    }
}
 
int cine;
 
void dfs3(int nod)
{
    if (deg[nod] == 1)
        l[cine].push_back(nod);
    else
    {
        for (auto fiu : f[nod])
            dfs3(fiu);
    }
}
 
void getleaves(int nod)
{
    cine = nod;
    dfs3(nod);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x,y;
        cin >> x >> y;
        deg[x]++;
        deg[y]++;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        if (deg[i] == 1)
            frunze++;
    int r;
    for (int i = 1; i <= n; i++)
        if (deg[i] > 1)
            r = i;
    dfs(r,0);
    r = findroot(r);
    dfs2(r,0);
    for (auto fiu : g[r])
        getleaves(fiu);
    priority_queue<pair<int,int>>pq;
    for (auto fiu : g[r])
        pq.push({l[fiu].size(),fiu});
    while (!pq.empty())
    {
        int nod = pq.top().second;
        pq.pop();
        if (pq.empty())
        {
            sol.push_back({r,l[nod].back()});
            break;
        }
        int nod2 = pq.top().second;
        pq.pop();
        sol.push_back({l[nod].back(),l[nod2].back()});
        l[nod].pop_back();
        l[nod2].pop_back();
        if (l[nod].size() != 0)
            pq.push({l[nod].size(),nod});
        if (l[nod2].size() != 0)
            pq.push({l[nod2].size(),nod2});
    }
    cout << sol.size() << '\n';
    for (auto it : sol)
        cout << it.first << ' ' << it.second << '\n';
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:98:17: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     r = findroot(r);
      |         ~~~~~~~~^~~

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