Submission #1270666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270666		BuzzyBeez	Network (BOI15_net)	C++20	100 / 100	328 ms	115304 KiB

net

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

vector<int> adj[500008], rem[500008];

void add_edge(int u, int v) {adj[u].push_back(v); adj[v].push_back(u);}

vector<pair<int, int>> ans;

int timer = 0;
void DFS(int u, int p) {
	bool is_leaf = 1; vector<pair<int, int>> Q, Q2;
	for (int v : adj[u]) if (v != p) {
		DFS(v, u); is_leaf = 0;
		for (int i : rem[v]) Q.emplace_back(v * (rem[v].size() == 1 ? 1 : -1), i);
	}
	sort(Q.begin(), Q.end());
	for (pair<int, int> item : Q) 
		if (!Q2.empty() && Q2.back().first != item.first) {
			ans.emplace_back(Q2.back().second, item.second);
			Q2.pop_back();
		}
		else Q2.emplace_back(item);
	if (is_leaf) rem[u].push_back(u);
	else if (Q2.empty()) {
		Q2 = {{0, ans.back().first}, {0, ans.back().second}};
		ans.pop_back();
	}
	for (pair<int, int> p : Q2) rem[u].push_back(p.second);
	Q.clear(); Q2.clear();
	// cout << ">> " << u << endl;
	// for (pair<int, int> p : ans) cout << p.first << ' ' << p.second << endl;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, u, v; cin >> n;
	for (int i = 1; i < n; ++i) cin >> u >> v, add_edge(u, v);
	if (n == 2) {
		cout << 1 << '\n' << 1 << ' ' << 2;
		return 0;
	}
	int rt = 1;
	while (adj[rt].size() == 1) ++rt;
	DFS(rt, 0); 
	while (rem[rt].size() > 1) {
		ans.emplace_back(*rem[rt].rbegin(), *(rem[rt].rbegin() + 1));
		rem[rt].pop_back(); rem[rt].pop_back();
	}
	if (!rem[rt].empty()) ans.emplace_back(rt, rem[rt][0]);
	cout << ans.size() << '\n';
	for (pair<int, int> p : ans) cout << p.first << ' ' << p.second << '\n';
}

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