Submission #1095444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095444		maxFedorchuk	Network (BOI15_net)	C++17	100 / 100	275 ms	47956 KiB

net

#include <bits/stdc++.h>
using namespace std;

const long long MX=5e5+10;

vector < int > mas[MX];
vector < int > lst;

void DFS(int zar,int mun)
{
    if(mas[zar].size()==1)
    {
        lst.push_back(zar);
        return;
    }

    for(auto u:mas[zar])
    {
        if(u!=mun)
        {
            DFS(u,zar);
        }
    }

    return;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n;
    cin>>n;

    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        mas[a].push_back(b);
        mas[b].push_back(a);
    }

    for(int i=1;i<=n;i++)
    {
        if(mas[i].size()>1)
        {
            DFS(i,0);
            break;
        }
    }

    vector < pair < int , int > > ans;
    int pol=lst.size()/2;

    for(int i=0;i<pol;i++)
    {
        ans.push_back({lst[i],lst[i+pol]});
    }

    if(lst.size()%2)
    {
        ans.push_back({lst[0],lst.back()});
    }


    cout<<ans.size()<<"\n";
    for(auto [a,b]:ans)
    {
        cout<<a<<" "<<b<<"\n";
    }

    return 0;
}

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