Submission #109404

#	Time	Username	Problem	Language	Result	Execution time	Memory
109404		IVIosab	Network (BOI15_net)	C++17	100 / 100	766 ms	47708 KiB

net

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj(500005);
vector<int> leafs;

void dfs(int curn,int prev){
    if(adj[curn].size()==1){
        leafs.push_back(curn);
    }
    for(int i=0;i<adj[curn].size();i++){
        if(adj[curn][i]!=prev){
            dfs(adj[curn][i],curn);
        }
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,-1);
    if(leafs.size()%2==0){
        cout<<leafs.size()/2<<"\n";
        for(int i=0;i<leafs.size()/2;i++){
            cout<<leafs[i]<<" "<<leafs[i+leafs.size()/2]<<"\n";
        }
    }
    else{
        cout<<leafs.size()/2+1<<"\n";
        for(int i=0;i<leafs.size()/2;i++){
            cout<<leafs[i]<<" "<<leafs[i+leafs.size()/2+1]<<"\n";
        }
        cout<<leafs[leafs.size()/2]<<" 1\n";
    }
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'void dfs(int, int)':
net.cpp:12:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[curn].size();i++){
                 ~^~~~~~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<leafs.size()/2;i++){
                     ~^~~~~~~~~~~~~~~
net.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<leafs.size()/2;i++){
                     ~^~~~~~~~~~~~~~~

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