Submission #310046

#	Time	Username	Problem	Language	Result	Execution time	Memory
310046		nicolaalexandra	Network (BOI15_net)	C++14	100 / 100	1096 ms	49812 KiB

net

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

vector <int> L[DIM],v;
int g[DIM];
int n,i,j,x,y,rad;

void dfs (int nod, int tata){
    int ok = 0;
    for (auto vecin : L[nod])
        if (vecin != tata){
            ok = 1;
            dfs (vecin,nod);
        }
    if (!ok)
        v.push_back(nod);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<n;i++){
        cin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
        g[x]++, g[y]++;
    }

    for (i=1;i<=n;i++)
        if (g[i] >= 2){
            rad = i;
            break;
        }

    dfs (rad,0);

    cout<<(v.size()+1)/2<<"\n";

    if (v.size() % 2){
        cout<<v[v.size()/2]<<" "<<rad<<"\n";
        j++;
    }

    i = 0, j += v.size()/2;
    while (j < v.size()){
        cout<<v[i]<<" "<<v[j]<<"\n";
        i++, j++;
    }

    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while (j < v.size()){
      |            ~~^~~~~~~~~~

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