Submission #47119

#	Time	Username	Problem	Language	Result	Execution time	Memory
47119		MatheusLealV	Network (BOI15_net)	C++17	0 / 100	3 ms	2828 KiB

net

#include <bits/stdc++.h>
#define N 100050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, qtd, tempo;

vector<int> grafo[N];

vector<pii> leaf;

void dfs(int x, int p)
{
	int ini = ++tempo;

	for(auto v: grafo[x])
	{
		if(v == p) continue;

		dfs(v, x);
	}

	if(grafo[x].size() == 1) leaf.push_back({tempo, x}), qtd ++;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

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

		grafo[a].push_back(b);

		grafo[b].push_back(a);
	}

	dfs(1, 1);

	sort(leaf.begin(), leaf.end());

	cout<<(qtd + 1)/2<<"\n";

	if( (qtd % 2 == 0) )
	{
		for(int i = 0; i < leaf.size()/2; i++)
			cout<<leaf[i].s<<" "<<leaf[leaf.size() - i - 1].s<<'\n';
	}

	else
	{
		for(int i = 0; i < leaf.size()/2; i++)
			cout<<leaf[i].s<<" "<<leaf[leaf.size() - i - 1].s<<'\n';

		cout<<leaf[qtd/2].s<<" "<<leaf[0].s<<"\n";
	}

}

Compilation message (stderr)

net.cpp: In function 'void dfs(int, int)':
net.cpp:16:6: warning: unused variable 'ini' [-Wunused-variable]
  int ini = ++tempo;
      ^~~
net.cpp: In function 'int main()':
net.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < leaf.size()/2; i++)
                  ~~^~~~~~~~~~~~~~~
net.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < leaf.size()/2; i++)
                  ~~^~~~~~~~~~~~~~~

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