Submission #67259

#	Time	Username	Problem	Language	Result	Execution time	Memory
67259		MatheusLealV	Network (BOI15_net)	C++17	100 / 100	1026 ms	155240 KiB

net

#include <bits/stdc++.h>
#define N 500050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
 
int n, ponte, cnt, id[N], menor[N], root;
 
vector<int> grafo[N], leaf;
 
void dfs(int x, int p)
{
	menor[x] = x;

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

		dfs(v, x);

		menor[x] = min(menor[x], menor[v]);
	}
}
 
void dfs2(int x, int p)
{
	vector<pii> order;

	if(grafo[x].size() == 1) leaf.push_back(x);

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

		order.push_back({menor[v], v});
	}

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

	for(auto v: order) dfs2(v.s, x);
}

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);
	}
 
 	for(int i = 1; i <= n; i++)
 	{
 		if(grafo[i].size() <= 1) continue;

 		root = i;

 		break;
 	}

 	dfs(root, root);

 	dfs2(root, root);

 	cout<<(ceil(leaf.size()/2.0))<<"\n";

 	for(int i = 0, j = ((leaf.size()/2)); i < (ceil(leaf.size()/2.0)); i++, j++)
 	{
 		cout<<leaf[i]<<" "<<leaf[j]<<"\n";
 	}
}

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