Submission #104660

#	Time	Username	Problem	Language	Result	Execution time	Memory
104660		Anai	Network (BOI15_net)	C++14	0 / 100	15 ms	12160 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];
int st[N], dr[N], aib[N], line[N], aux[N];
bool matched[N];

vector<pii> ant;
set<pii> leaves;
int n, root, connector;


static int lsb(const int &x) {
	return x & -x; }

static int query(int pos) {
	int ant = 0;
	for (; pos > 0; pos-= lsb(pos))
		ant+= aib[pos];
	return ant; }

static void update(int pos, int val) {
	for (; pos < N; pos+= lsb(pos))
		aib[pos]+= val; }

static void dfs(int u) {
	static int lptr = 0; ++lptr;
	line[lptr] = u;
	st[u] = lptr;
	for (auto v: g[u]) {
		g[v].erase(remove(begin(g[v]), end(g[v]), u), end(g[v]));
		dfs(v); }
	dr[u] = lptr; }

static void solve(int u) {
	if (g[u].empty()) // I'm a leaf
		return;

	aux[u] = query(dr[u]) - query(st[u] - 1);
	for (auto v: g[u])
		aux[v] = query(dr[v]) - query(st[v] - 1);
	g[u].erase(remove_if(begin(g[u]), end(g[u]), [&](const int &nod) { return aux[nod] == 0; }), end(g[u])); // remove solved subtrees
	if (g[u].size() == 1) { // I'm an intermediar
		solve(g[u][0]);
		return; }

	if (aux[u] % 2) { // get read of the odd case (remove one, ignore other ---- may only happen at root)
		int a = g[u][0], b = g[u][1];

		auto ita = leaves.lower_bound(pii(st[a], 0));
		auto itb = leaves.lower_bound(pii(st[b], 0));

		ant.emplace_back(ita->second, itb->second);
		update(ita->first, -1);
		leaves.erase(ita);
		aux[a]-= 1;
		solve(u);
		return; }

	sort(begin(g[u]), end(g[u]), [&](const int &a, const int &b) {
		return aux[a] > aux[b]; });

	for (int i = 0; i + 1 < g[u].size(); i+= 2) { // pair consecutive elements
		int a = g[u][i], b = g[u][i + 1];

		auto ita = leaves.lower_bound(pii(st[a], 0));
		auto itb = leaves.lower_bound(pii(st[b], 0));

		ant.emplace_back(ita->second, itb->second);
		update(ita->first, -1);
		update(itb->first, -1);
		leaves.erase(ita);
		leaves.erase(itb);
		aux[a]-= 1;
		aux[b]-= 1; }

	if (g[u].size() % 2 == 1) { // pair the last one left if it's the case
		int a = g[u].back(), b = g[u][0];

		auto ita = leaves.lower_bound(pii(st[a], 0));
		auto itb = leaves.lower_bound(pii(st[b], 0));

		assert(ita->second <= dr[a]);
		assert(itb->second <= dr[b]);

		ant.emplace_back(ita->second, itb->second);
		update(ita->first, -1);
		update(itb->first, -1);
		leaves.erase(ita);
		leaves.erase(itb);
		aux[a]-= 1;
		aux[b]-= 1; }		

	g[u].erase(remove_if(begin(g[u]), end(g[u]), [&](const int &nod) { return aux[nod] == 0; }), end(g[u])); // get rid of solved ones
	auto it = partition(begin(g[u]), end(g[u]), [&](const int &nod) { return aux[nod] % 2; });

	for (int i = 0; i + 1 < g[u].size() && aux[g[u][i + 1]] % 2 == 1; i+= 2) { // make the odds even
		int a = g[u][i], b = g[u][i + 1];

		auto ita = leaves.lower_bound(pii(st[a], 0));
		auto itb = leaves.lower_bound(pii(st[b], 0));

		ant.emplace_back(ita->second, itb->second);
		update(ita->first, -1);
		update(itb->first, -1);
		leaves.erase(ita);
		leaves.erase(itb);
		aux[a]-= 1;
		aux[b]-= 1; }

	sort(begin(g[u]), end(g[u]), [&](const int &a, const int &b) {
		return aux[a] < aux[b]; });

	for (int i = 0; i + 1 < g[u].size(); i+= 2) {
		int a = g[u][i], b = g[u][i + 1];
		while (aux[a] && aux[b]) {
			auto ita = leaves.lower_bound(pii(st[a], 0));
			auto itb = leaves.lower_bound(pii(st[b], 0));

			ant.emplace_back(ita->second, itb->second);
			update(ita->first, -1);
			update(itb->first, -1);
			leaves.erase(ita);
			leaves.erase(itb);
			aux[a]-= 1;
			aux[b]-= 1; } }

	for (auto v: g[u]) if (aux[v])
		solve(v); }


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);
	for (int i = 1; i <= n; ++i)
		if (g[i].empty()) {
			leaves.emplace(st[i], i);
			update(st[i], 1); }

	int l = leaves.size();
	solve(root);

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

	return 0; }

Compilation message (stderr)

net.cpp: In function 'void solve(int)':
net.cpp:70:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i + 1 < g[u].size(); i+= 2) { // pair consecutive elements
                  ~~~~~~^~~~~~~~~~~~~
net.cpp:104:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i + 1 < g[u].size() && aux[g[u][i + 1]] % 2 == 1; i+= 2) { // make the odds even
                  ~~~~~~^~~~~~~~~~~~~
net.cpp:121:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i + 1 < g[u].size(); i+= 2) {
                  ~~~~~~^~~~~~~~~~~~~
net.cpp:102:7: warning: variable 'it' set but not used [-Wunused-but-set-variable]
  auto it = partition(begin(g[u]), end(g[u]), [&](const int &nod) { return aux[nod] % 2; });
       ^~
net.cpp: In function 'int main()':
net.cpp:160:6: warning: unused variable 'l' [-Wunused-variable]
  int l = leaves.size();
      ^

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