Submission #47120

#	Time	Username	Problem	Language	Result	Execution time	Memory
47120		MatheusLealV	Network (BOI15_net)	C++17	0 / 100	3 ms	2684 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;

int sz[N], block[N], tot, proc[N], visit[N], cnt, ans = N;

pii best;

int tam(int x, int p)
{
	sz[x] = 1;

	for(auto v: grafo[x]) if(v!= p && !block[v]) sz[x] += tam(v, x);

	return sz[x]; 
}

void Split(int x, int p)
{
	int maior = tot - sz[x];

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

		Split(v, x);

		maior = max(maior, sz[v]);
	}

	if(maior < best.s) best = pii(x, maior); 
}

int find_centroid(int x)
{
	tot = tam(x, x);

	best = pii(N, N);

	Split(x, x);

	return best.f;
}

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);
	}

	int root = 1;

	for(int i = 1; i <= n; i++) if(grafo[i].size() > 1) root = i;

	dfs(root, root);

	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:56:6: warning: unused variable 'ini' [-Wunused-variable]
  int ini = ++tempo;
      ^~~
net.cpp: In function 'int main()':
net.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < leaf.size()/2; i++)
                  ~~^~~~~~~~~~~~~~~
net.cpp:101: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