Submission #655941

#	Time	Username	Problem	Language	Result	Execution time	Memory
655941		aebov	Network (BOI15_net)	C++17	100 / 100	590 ms	40912 KiB

net

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<utility>
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

const int N = (int)5e5 + 5;
int n , u, v, ind[N], _id = 0, root = 1;
vector<int> leafs;
vector<pii> ret;
vector<int> adj[N]; 

void dfs(int v,int p){
	ind[v] = _id ++;
	for(auto u : adj[v])if(u != p)dfs(u , v);
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i < n ; i ++){
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(int i = 1; i <= n; i ++)if(adj[i].size() > 1)root = i;
	dfs(root, root);
	for(int i = 1; i <= n; i ++){
		if(adj[i].size() == 1)ret.pb({ind[i], i});
	}
	sort(ret.begin(), ret.end());
	int sz= ret.size();
	cout << ((sz + 1) >> 1) << endl;
	for(int i = 0; i < sz/2; i ++)	cout << ret[i].S << " " << ret[i + (sz+1)/2].S << endl;
	if(sz&1) cout << ret[sz/2].S << " " << root << endl;
	exit(0);
} 

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