Submission #1282822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282822		Faisal_Saqib	Network (BOI15_net)	C++20	100 / 100	583 ms	109940 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+10;
vector<int> ma[N];
int par[N],hei[N];
bool path[N],isleaf[N];
// vector<int> cur;
vector<pair<int,int>> ans;
vector<int> leafs[N];
int mx=-1,end_point=-1;
void dfs(int x,int p=-1,int h=1)
{
    bool leaf=1;
    par[x]=p;
    hei[x]=h;
    for(auto y:ma[x])
    {
        if(y==p)continue;
        leaf=0;
        dfs(y,x,h+1);
    }
    if(leaf)
    {
        isleaf[x]=1;
        leafs[x].push_back(x);
        if(h>mx)
        {
            mx=h;
            end_point=x;
        }
    }
}
// void dfs_(int x,int p=-1,int h=1)
// {
//     for(auto y:ma[x])
//     {
//         if(y==p or path[y])continue;
//         dfs_(y,x,h+1);
//     }
//     if(isleaf[x])
//     {
//         leafs.push_back(x);
//     }
// }

int main()
{
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        ma[x].push_back(y);
        ma[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(ma[i].size()==1)
        {
            leafs[i].push_back(i);
            dfs(i);
            break;
        }
    }
    vector<pair<int,int>> ord;
    for(int i=1;i<=n;i++)
    {
        ord.push_back({hei[i],i});
    }
    sort(rbegin(ord),rend(ord));
    // for(int e=end_point;e!=-1;e=par[e])
    // {
    //     path[e]=1;
    // }
    // for(int i=0;i<n;i++)
    // {
    for(auto jtp:ord) // order by height
    {
        int j=jtp.second;
        if(leafs[j].size()==0 or par[j]==-1)continue;
        // j -> par[j]
        while(leafs[j].size()>0 and leafs[par[j]].size()>0 and leafs[j].size()+leafs[par[j]].size()>=3)
        {
            int x=leafs[j].back();
            int y=leafs[par[j]].back();
            leafs[j].pop_back();
            leafs[par[j]].pop_back();
            ans.push_back({x,y});
        }
        while(leafs[j].size())
        {
            leafs[par[j]].push_back(leafs[j].back());
            leafs[j].pop_back();
        }
    }
    for(int i=1;i<=n;i++)
    {
        // cout<<"Leafs at "<<i<<endl;
        // for(auto j:leafs[i])cout<<j<<' ';
        // cout<<endl;
        if(leafs[i].size())
        {
            ans.push_back({leafs[i].back(),i});
        }
        // cout<<leafs[i].size()<<' ';
    }
    // cout<<endl;
    // i
    // }
    
    cout<<ans.size()<<endl;
    for(auto i:ans)
    {
        cout<<i.first<<' '<<i.second<<endl;
    }
}

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