Submission #394636

#	Time	Username	Problem	Language	Result	Execution time	Memory
394636		negar_a	Network (BOI15_net)	C++14	100 / 100	498 ms	53200 KiB

net

//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 5e5 + 5;
vector <int> adj[maxn];
int st[maxn];
int tim = 0;

void dfs(int v, int p = -1){
	st[v] = tim;
	tim ++;
	for(int u : adj[v]){
		if(u != p){
			dfs(u, v);	
		}
	}
}

int main(){
	fast_io;
	int n;
	cin >> n;
	for(int i = 0; i < n - 1; i ++){
		int x, y;
		cin >> x >> y;
		x --; y --;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	int l = 0;
	int r = 0;
	for(int i = 0; i < n; i ++){
		if((int)adj[i].size() == 1){
			l ++;
		}else{
			r = i;
		}
	}
	dfs(r);
	vector <pii> vec;
	for(int i = 0; i < n; i ++){
		if((int)adj[i].size() == 1){
			vec.pb({st[i], i + 1});
		}
	}
	sort(vec.begin(), vec.end());
	cout << (l + 1) / 2 << '\n';
	for(int i = 0; i < l / 2; i ++){
		cout << vec[i].S << " " << vec[i + l / 2].S << '\n';
	}
	if(l % 2){
		cout << vec[l - 1].S << " " << vec[0].S << '\n';
	}
	
	return 0;
}

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