Submission #51366

#	Time	Username	Problem	Language	Result	Execution time	Memory
51366		faishol27	Network (BOI15_net)	C++14	0 / 100	21 ms	23912 KiB

net

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

typedef pair<int, int> pi;
#define PUB push_back
#define fi first
#define se second

int N, root = 1, cnt = 0, tot_leaf = 0, first_leaf = -1;
vector<int> adjL[500005], leaf[500005];
pi data[500005]; // {id, byk_leaf}

void find_root(){
	for(int i=1;i<=N;i++){
		if(adjL[i].size() > adjL[root].size()){
			root = i;
		}
	}
}

void find_leaf(int prn, int pos){
	if(adjL[pos].size() == 1){
		leaf[cnt].PUB(pos);
		tot_leaf++;
		data[cnt].se++;

		return;
	}

	for(auto nxt:adjL[pos]){
		if(nxt == prn) continue;
		find_leaf(pos, nxt);
	}
}

bool cmp(pi a, pi b){
	return a.se > b.se;
}

void print_ans(){
	int pos = 1, kanan = cnt-1;
	
	cout << (tot_leaf+1)/2 << endl;
	for(int i=0;i<cnt;i++){
		if(data[i].se == 0) continue;
		
		pos = max(pos, i+1);

		while(data[i].se > 0 && data[pos].se > 0){
			int a = leaf[data[i].fi].back(),
				b = leaf[data[pos].fi].back();
			cout << a << " " << b << endl;

			leaf[data[pos].fi].pop_back(); leaf[data[i].fi].pop_back();
			data[pos].se--; data[i].se--;

			pos++;
			if(pos > kanan){
				while(data[kanan].se == 0){
					kanan--;
				}
				
				pos = i+1;
			}
		}

		while(data[i].se > 0){
			if(data[i].se == 1){
				cout << leaf[data[i].fi].back() << " " << first_leaf << endl;
				data[i].se--;
			}else{
				cout << leaf[data[i].fi].back(); leaf[data[i].fi].pop_back();
				cout << " " << leaf[data[i].fi].back() << endl; leaf[data[i].fi].pop_back();
				data[i].se -= 2;
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	for(int i=0;i<N-1;i++){
		int x, y;
		cin >> x >> y;
		
		adjL[x].PUB(y);
		adjL[y].PUB(x);
	}

	find_root();

	for(auto nxt:adjL[root]){
		data[cnt] = {cnt, 0};
		find_leaf(root, nxt);
		cnt++;
	}

	sort(data, data+cnt, cmp);
	first_leaf = leaf[data[0].fi].back();

	// cerr << "root: " << root << endl;
	// cerr << "first: " << first_leaf << endl;
	// for(int i=0;i<cnt;i++){
	// 	cerr << data[i].se << " -> ";
	// 	for(auto elm:leaf[data[i].fi]) cerr << " " << elm;
	// 	cerr << endl;
	// }

	print_ans();

	return 0;
}

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