Submission #102150

#	Time	Username	Problem	Language	Result	Execution time	Memory
102150		Leonardo_Paes	Network (BOI15_net)	C++11	100 / 100	625 ms	41036 KiB

net

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 100;

int v[MAXN], cnt;

vector<int> grafo[MAXN];

int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}

void dfs(int u, int p)
{
	for (int i=0; i<grafo[u].size(); i++){
        int v = grafo[u][i];
		if (v == p) continue;
		dfs(v, u);
	}

	if (grafo[u].size() == 1) v[++cnt] = u;
}

int main(){
    ios_base::sync_with_stdio(false);cout.tie(NULL);
    int n=read();

    for(int i=1; i<n; i++){
        int a, b;

        a=read();
        b=read();

        grafo[a].push_back(b);
        grafo[b].push_back(a);
    }

    for(int i=1; i<=n; i++){
        if(grafo[i].size()>1){
            dfs(i, 0);
            break;
        }
    }

    int ans = (cnt+1)/2;

    cout << ans << "\n";

    for(int i=1; i<ans; i++){
        cout << v[i] << " " << v[i+ans] << "\n";
    }
    if(cnt&1){
        cout << v[ans] << " " << v[1] << "\n";
    }
    else{
        cout << v[ans] << " " << v[cnt] << "\n";
    }
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'void dfs(int, int)':
net.cpp:21:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<grafo[u].size(); i++){
                ~^~~~~~~~~~~~~~~~

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