Submission #203572

#	Time	Username	Problem	Language	Result	Execution time	Memory
203572		mdn2002	Network (BOI15_net)	C++14	100 / 100	1172 ms	47732 KiB

net

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>lf,gr[500005];
void dfs(int x,int p)
{
    if(gr[x].size()==1)lf.push_back(x);
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i];
        if(u==p)continue;
        dfs(u,x);
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    dfs(1,0);
    cout<<lf.size()/2+(lf.size()%2)<<endl;
    for(int i=0;i<lf.size()/2;i++)
    {
        cout<<lf[i]<<' '<<lf[i+(lf.size()/2)]<<endl;
    }
    if(lf.size()%2)cout<<lf[0]<<' '<<lf[lf.size()-1]<<endl;
}

Compilation message (stderr)

net.cpp: In function 'void dfs(int, int)':
net.cpp:8:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[x].size();i++)
                 ~^~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<lf.size()/2;i++)
                 ~^~~~~~~~~~~~

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