Submission #159789

#	Time	Username	Problem	Language	Result	Execution time	Memory
159789		cookiedoth	Network (BOI15_net)	C++14	100 / 100	977 ms	98716 KiB

net

/*

Code for problem net by cookiedoth
Generated 24 Oct 2019 at 05.47 P


   ,##.                   ,==.
 ,#    #.                 \ o ',
#        #     _     _     \    \
#        #    (_)   (_)    /    ; 
 `#    #'                 /   .'  
   `##'                   "=="

¯\_(ツ)_/¯
^_^
~_^

*/

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define sz(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int mx = 5e5 + 228;
int n, root, deg[mx], sz[mx];
vector<vector<int> > g;

void calc_sz(int v, int pv) {
	for (auto v1 : g[v]) {
		if (v1 != pv) {
			calc_sz(v1, v);
			sz[v] += sz[v1];
		}
	}
	sz[v] += (deg[v] == 1);
}

int find_leaf_centroid(int v, int pv) {
	for (auto v1 : g[v]) {
		if (v1 != pv && 2 * sz[v1] > sz[root] + 1) {
			return find_leaf_centroid(v1, v);
		}
	}
	return v;
}

void find_leaves(int v, int pv, vector<int> &res) {
	// cerr << "find_leaves " << v << " " << pv << endl;
	if (deg[v] == 1) {
		res.push_back(v);
	}
	for (auto v1 : g[v]) {
		if (v1 != pv) {
			find_leaves(v1, v, res);
		}
	}
}

set<pair<int, int> > s;
vector<vector<int> > a;

void pop_back(pair<int, int> pp) {
	s.erase(pp);
	pp.first--;
	s.insert(pp);
	a[pp.second].pop_back();
}

void solve() {
	root = -1;
	for (int i = 0; i < n; ++i) {
		if (deg[i] > 1) {
			root = i;
		}
	}
	calc_sz(root, root);
	int c = find_leaf_centroid(root, root);

	assert(deg[c] > 1);

	// cerr << "c = " << c << endl;

	int all_leaves = 0;
	for (int i = 0; i < g[c].size(); ++i) {
		int v = g[c][i];
		vector<int> cur;
		find_leaves(v, c, cur);

		// cerr << "cur" << endl;
		// output(all(cur));

		a.push_back(cur);
		all_leaves += cur.size();
		s.insert({cur.size(), i});
	}

	vector<pair<int, int> > ans;
	for (int i = 0; i < (all_leaves + 1) / 2; ++i) {
		int id1 = prev(s.end())->second, id2 = prev(prev(s.end()))->second;
		// cerr << "id " << id1 << " " << id2 << endl;
		ans.emplace_back(a[id1].back(), a[id2].back());
		pair<int, int> pp1 = (*prev(s.end())), pp2 = (*prev(prev(s.end())));
		pop_back(pp1);
		if (!(i == 0 && all_leaves % 2)) {
			pop_back(pp2);
		}
	}

	cout << ans.size() << "\n";
	for (auto pp : ans) {
		cout << pp.first + 1 << " " << pp.second + 1 << "\n";
	}
}

signed main() {
	fast_io();
	cin >> n;
	g.resize(n);
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		g[u].push_back(v);
		g[v].push_back(u);
		deg[u]++;
		deg[v]++;
	}
	solve();
}

Compilation message (stderr)

net.cpp: In function 'void solve()':
net.cpp:146:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[c].size(); ++i) {
                  ~~^~~~~~~~~~~~~

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