Submission #476658

#	Time	Username	Problem	Language	Result	Execution time	Memory
476658		thiago_bastos	Network (BOI15_net)	C++17	0 / 100	1 ms	204 KiB

net

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

using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

vector<vector<int>> g;
vector<int> leaves;
int n;

void preprocess(int u, int p = -1) {
	leaves[u] = 0;
	if((int)g[u].size() == 1) ++leaves[u];
	for(int v : g[u]) {
		if(v == p) continue;
		preprocess(v, u);
		leaves[u] += leaves[v];
	}
}

int dfs(int u, int p = -1) {
	
	int max_leaves = 0;
	
	if(p != -1) max_leaves = leaves[0] - leaves[u];
	
	for(int v : g[u]) {
		if(v == p) continue;
		max_leaves = max(max_leaves, leaves[v]);
	}
	
	if(max_leaves <= leaves[0] / 2) return u;
	
	for(int v : g[u]) {
		if(v == p) continue;
		int w = dfs(v, u);
		if(w != -1) return w;
	}
	
	return -1;
}

void solve() {
	cin >> n;
	
	g.resize(n);
	leaves.resize(n);
	
	for(int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	preprocess(0);
  
	int v = dfs(0);
	
	vector<vector<int>> F;
	vector<int> P;
	
	function<void(vector<int>&, int, int)> get = [&](vector<int>& f, int u, int p) {
		if(g[u].size() == 1) f.push_back(u);
		else {
			for(int v : g[u]) {
				if(v == p) continue;
				get(f, v, u);
			}
		}
	};
		
	for(int u : g[v]) {
		F.push_back({});
		get(F.back(), u, v);
	}
	
	P.resize(F.size());
	iota(P.begin(), P.end(), 0);
	sort(P.begin(), P.end(), [&F](int e, int d) {
		return F[e].size() < F[d].size();
	});
	
	vector<ii> pairs;
	
	int lo = 0, hi = (int)F.size() - 1;
	
	while(lo < hi) {
		int u = F[P[lo]].back();
		int v = F[P[hi]].back();
		pairs.emplace_back(u + 1, v + 1);
		F[P[lo]].pop_back();
		F[P[hi]].pop_back();
		if(F[P[lo]].empty()) ++lo;
		if(F[P[hi]].empty()) --hi;
	}
	
	for(auto& x : F) {
		if(x.empty()) continue;
		int u = x.back();
		sort(g[u].begin(), g[u].end());
		if(g[u][0]) pairs.emplace_back(u + 1, 1);
		else if(g[u].back() < n - 1) pairs.emplace_back(u + 1, n);
		else {
			for(int i = 1; i < (int)g[u].size(); ++i) {
				if(g[u][i] - g[u][i - 1] > 1) {
					pairs.emplace_back(u + 1, g[u][i - 1] + 1);
					break;
				}
			}
		}
		break;
	}
	
	cout << pairs.size() << '\n';
	for(auto [u, v] : pairs) cout << u << ' ' << v << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
 	return 0;
}

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