Submission #49590

#	Time	Username	Problem	Language	Result	Execution time	Memory
49590		rzbt	Network (BOI15_net)	C++14	100 / 100	922 ms	153276 KiB

net

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

int n,in1,in2,tren,prethodni,duz,koren=0;
vector<vector<int> > drvo;
stack<pair<int,int> > dfs;
pair<int,int> vrh;
vector<int> listovi;

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    drvo.resize(n+1);
    for(int i=1;i<n;i++)
    {
        cin>>in1>>in2;
        drvo[in1].push_back(in2);
        drvo[in2].push_back(in1);
    }
    if(n<=20)
    {
        if(n==1)
        {
            cout<<1<<endl<<1<<" "<<1;
        }
        if(n==2)
        {
            cout<<1<<endl<<1<<" "<<2;
            return 0;
        }
        for(int i=1;i<=n;i++)
        {
            if(drvo[i].size()>1)
            {
                dfs.push(make_pair(i,0));
                break;
            }
        }
        while(!dfs.empty())
        {
            vrh=dfs.top();
            dfs.pop();
            tren=vrh.first;
            prethodni=vrh.second;
            duz=drvo[tren].size();
            if(duz==1)
            {
                listovi.push_back(tren);
            }
            else
            {
                for(int i=0;i<duz;i++)
                {
                    if(drvo[tren][i]!=prethodni)
                    {
                        dfs.push(make_pair(drvo[tren][i],tren));
                    }
                }
            }
        }
        duz=listovi.size();
        cout<<(duz+1)/2<<endl;
        for(int i=0;i<(duz+1)/2;i++)
        {
            if(i==duz-i-1)
            {
                cout<<listovi[0]<<" "<<listovi[i]<<endl;
            }
            else
            {
                cout<<listovi[i]<<" "<<listovi[i+(duz+1)/2]<<endl;
            }
        }
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(drvo[i].size()>1)
        {
            dfs.push(make_pair(i,0));
            break;
        }
    }
    while(!dfs.empty())
    {
        vrh=dfs.top();
        dfs.pop();
        tren=vrh.first;
        prethodni=vrh.second;
        duz=drvo[tren].size();
        if(duz==1)
        {
            listovi.push_back(tren);
        }
        else
        {
            for(int i=0;i<duz;i++)
            {
                if(drvo[tren][i]!=prethodni)
                {
                    dfs.push(make_pair(drvo[tren][i],tren));
                }
            }
        }
    }
    duz=listovi.size();
    cout<<(duz+1)/2<<endl;
    for(int i=0;i<(duz+1)/2;i++)
    {
        if(i==duz-i-1)
        {
            cout<<listovi[0]<<" "<<listovi[i]<<endl;
        }
        else
        {
            cout<<listovi[i]<<" "<<listovi[(duz+1)/2+i]<<endl;
        }
    }
}

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