Submission #51623

#	Time	Username	Problem	Language	Result	Execution time	Memory
51623		faishol27	Network (BOI15_net)	C++14	0 / 100	31 ms	23916 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];
vector<pi> leaf[500005]; //{indeks, dist}
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, int dist){
	if(adjL[pos].size() == 1){
		leaf[cnt].PUB({pos, dist});
		tot_leaf++;
		data[cnt].se++;
 
		return;
	}
 
	for(auto nxt:adjL[pos]){
		if(nxt == prn) continue;
		find_leaf(pos, nxt, dist+1);
	}
}
 
bool cmp(pi a, pi b){
	return a.se > b.se;
}

bool cmp_leaf(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().fi,
				b = leaf[data[pos].fi].back().fi;
			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().fi << " " << first_leaf << endl;
				data[i].se--;
			}else{
				cout << leaf[data[i].fi].back().fi; leaf[data[i].fi].pop_back();
				cout << " " << leaf[data[i].fi].back().fi << 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, 1);
		cnt++;
	}
 
	sort(data, data+cnt, cmp);
	for(int i=0;i<cnt;i++){
		if(!leaf[i].empty()) sort(leaf[i].begin(), leaf[i].end(), cmp_leaf);
	}

	first_leaf = leaf[data[0].fi].back().fi;
 
	// 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.fi << "," << elm.se << "]";
	// 	cerr << endl;
	// }
 
	print_ans();
 
	return 0;
}

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