Submission #467066

#	Time	Username	Problem	Language	Result	Execution time	Memory
467066		_Avocado_	Network (BOI15_net)	C++14	100 / 100	555 ms	57500 KiB

net

#include <bits/stdc++.h>
#define int int64_t
using namespace std;

vector<vector<int>>graph;
vector<int>dist;
vector<int>leaf;

void dfs(int v, int p){
	dist[v] = dist[p] + 1;
	
	if(graph[v].size() == 1) leaf.push_back(v);
	
	for(auto u: graph[v]){
		if(u != p) dfs(u, v);
	}
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n; cin>>n;
	
	graph.assign(n, vector<int>());
	dist.assign(n, -1);
	
	for(int i = 0; i<n-1; ++i){
		int a, b; cin>>a>>b;
		--a; --b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	
	dfs(0, 0);
	
	int m = leaf.size();
	/*
	for(auto u: leaf) cout<<u<<" ";
	cout<<endl;
	for(auto u: dist) cout<<u<<" ";
	cout<<endl;
	*/
	
	vector<pair<int, int>>fred;
	
	for(auto u: leaf){
		fred.push_back({dist[u], u});
	}
	
	sort(fred.begin(), fred.end());
	/*
	for(auto [x, y]: fred) cout<<y<<" ";
	cout<<endl;
	*/
	
	cout<<(m+1)/2<<'\n';
	
	for(int i = 0; i<m/2; ++i){
		cout<<leaf[i]+1<<" "<<leaf[m/2+i]+1<<'\n';
	}
	
	if(leaf.size()%2) cout<<leaf[m/2]+1<<" "<<leaf[m-1]+1<<'\n';


	//cout<<'\n';
}

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