Submission #104668

#	Time	Username	Problem	Language	Result	Execution time	Memory
104668		Anai	Network (BOI15_net)	C++14	100 / 100	963 ms	69472 KiB

net

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using pii = pair<int, int>;

const int N = 5e5 + 5;


vector<int> g[N], lvs[N];
bool matched[N];

vector<pii> ant;
int n, root;


static void dfs(int u) {
	if (g[u].empty())
		lvs[u].push_back(u);

	int total = 0;

	for (auto v: g[u]) {
		g[v].erase(remove(begin(g[v]), end(g[v]), u), end(g[v]));
		dfs(v);
		total+= lvs[v].size(); }

	sort(begin(g[u]), end(g[u]), [&](const int &a, const int &b) {
		return lvs[a].size() > lvs[b].size(); });
	if (g[u].size() == 1)
		swap(lvs[g[u][0]], lvs[u]);

	for (auto v: g[u]) {
		while (lvs[u].size() && lvs[v].size() && total > (u == root ? 0 : 2)) {
			ant.emplace_back(lvs[u].back(), lvs[v].back());
			lvs[u].pop_back();
			lvs[v].pop_back();
			total-= 2; }
		while (lvs[v].size()) {
			lvs[u].push_back(lvs[v].back());
			lvs[v].pop_back(); } } }

int main() {
#ifdef HOME
	freopen("network.in", "r", stdin);
	freopen("network.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int u, v, i = 1; i < n; ++i) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u); }

	for (root = 1; g[root].size() == 1; ++root);
	dfs(root);

	if (lvs[root].size())
		ant.emplace_back(root, lvs[root][0]);

	cout << ant.size() << '\n';
	for (auto i: ant)
		cout << i.x << ' ' << i.y << '\n';

	return 0; }

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