Submission #630405

#	Time	Username	Problem	Language	Result	Execution time	Memory
630405		MasterTaster	Network (BOI15_net)	C++14	0 / 100	6 ms	11988 KiB

net

#include <bits/stdc++.h>
 
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 500010
 
using namespace std;
 
int n;
vector<int> g[MAXN], listovi;
bool bio[MAXN];
 
void dfs(int u)
{
    bio[u]=true;
    if (g[u].size()==1) listovi.pb(u);
    for (auto v:g[u]) if (!bio[v]) dfs(v);
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    cin>>n;
    if (n==1) { cout<<1<<endl<<1<<" "<<1; exit(0); }
    if (n==2) { cout<<1<<endl<<1<<" "<<2; exit(0); }
 
    for (int i=1; i<n; i++)
    {
        int u, v; cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
 
    for (int i=1; i<n; i++) if (g[i].size()!=1) { dfs(i); break; }
 
    //for (int i=0; i<listovi.size(); i++) cout<<listovi[i]<<" ";
 
    cout<<(listovi.size()+1)/2<<endl;
    for (int i=0; i<listovi.size()/2; i++)
    {
        cout<<listovi[i]<<" "<<listovi[i+listovi.size()/2]<<endl;
    }
    if (listovi.size()%2) cout<<listovi[listovi.size()-2]<<" "<<listovi[listovi.size()-1];
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i=0; i<listovi.size()/2; i++)
      |                   ~^~~~~~~~~~~~~~~~~

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