Submission #643760

#	Time	Username	Problem	Language	Result	Execution time	Memory
643760		ymm	Network (BOI15_net)	C++17	100 / 100	837 ms	94692 KiB

net

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 500'010;
vector<int> A[N];
int rt = 0;
int cnt[N];
int n;

int dfs1(int v, int p)
{
	cnt[v] = A[v].size() == 1;
	for (int u : A[v]) {
		if (u != p)
			cnt[v] += dfs1(u, v);
	}
	return cnt[v];
}

int dfs2(int v, int p, int tot)
{
	for (int u : A[v]) {
		if (u == p)
			continue;
		if (cnt[u] > tot - cnt[u])
			return dfs2(u, v, tot);
	}
	return v;
}

vector<int> leaves[N];

void dfs3(int v, int p, vector<int> &vec)
{
	if (A[v].size() == 1)
		vec.push_back(v);
	for (int u : A[v])
		if (u != p)
			dfs3(u, v, vec);
}

bool cmp(vector<int> *a, vector<int> *b) {
	return a->size() > b->size();
}

multiset<vector<int>*, bool (*)(vector<int>*, vector<int>*)> s(cmp);

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	while (A[rt].size() == 1) ++rt;
	dfs1(rt, -1);
	rt = dfs2(rt, -1, cnt[rt]);
	for (int v : A[rt]) {
		dfs3(v, rt, leaves[v]);
		s.insert(&leaves[v]);
	}
	vector<pii> ans;
	for (;;) {
		auto v1 = *s.begin();
		s.erase(s.begin());
		if (v1->size() == 0)
			break;
		auto v2 = *s.begin();
		s.erase(s.begin());
		if (v2->size() == 0) {
			ans.push_back({rt, v1->front()});
			break;
		}
		ans.push_back({v1->back(), v2->back()});
		v1->pop_back();
		v2->pop_back();
		s.insert(s.begin(), v1);
		s.insert(s.begin(), v2);
	}
	cout << ans.size() << '\n';
	for (auto [v, u] : ans)
		cout << v+1 << ' ' << u+1 << '\n';
}

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