Submission #723232

#	Time	Username	Problem	Language	Result	Execution time	Memory
723232		gagik_2007	Village (BOI20_village)	C++17	56 / 100	226 ms	156788 KiB

Village

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll M = 307;
const ll LG = 31;
ll n, m, k;
vector<int>g[N];
vector<int>res_mn, res_mx;
ll ans_mn = 0, ans_mx = 0;
bool used[N];
int sz[N];
stack<int>st[N];
bool useds[N];

bool comp(int x, int y) {
	return st[x].size() < st[y].size();
}

multiset<int, decltype(&comp)> s(&comp);

void dfs(int v, int par = -1) {
	for (int to : g[v]) {
		if (to != par) {
			dfs(to, v);
		}
	}
	vector<int>leaves;
	for (int to : g[v]) {
		if (to != par) {
			if (!used[to]) {
				leaves.push_back(to);
			}
		}
	}
	if (leaves.size() != 0) {
		ans_mn += leaves.size() * 2;
		res_mn[v] = leaves[0];
		for (int i = 0; i < leaves.size() - 1; i++) {
			res_mn[leaves[i]] = leaves[i + 1];
		}
		res_mn[leaves[leaves.size() - 1]] = v;
		for (int to : leaves) {
			used[to] = true;
		}
		used[v] = true;
	}
}

void calc_sz(int v, int par = -1) {
	sz[v] = 1;
	for (int to : g[v]) {
		if (to != par) {
			calc_sz(to, v);
			sz[v] += sz[to];
		}
	}
	if (par != -1) {
		ans_mx += 2 * min(ll(sz[v]), n - sz[v]);
	}
}

int centroid(int v, int par = -1) {
	for (int to : g[v]) {
		if (to != par) {
			if (sz[to] > n / 2) {
				return centroid(to, v);
			}
		}
	}
	return v;
}

void inch_tenum_es_qci_stacki_mej(int v, int par, int cur) {
	if (!useds[v])st[cur].push(v);
	for (int to : g[v]) {
		if (to != par) {
			inch_tenum_es_qci_stacki_mej(to, v, cur);
		}
	}
}

int main() {
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int leaf = 0;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int v = 1; v <= n; v++) {
		if (g[v].size() == 1) {
			leaf = v;
			break;
		}
	}
	int root = g[leaf][0];
	res_mn.resize(n + 1, 0);
	res_mx.resize(n + 1, 0);
	dfs(root);
	calc_sz(1);
	int c = centroid(1);
	if (n % 2 != 0) {
		int cur_stack = 0;
		for (int to : g[c]) {
			inch_tenum_es_qci_stacki_mej(to, c, cur_stack++);
		}
		int maxim = 0;
		for (int i = 0; i < cur_stack; i++) {
			if (comp(maxim, i)) {
				maxim = i;
			}
			//cout << i << ": " << st[i].size() << endl;
		}
		int v1 = st[maxim].top();
		st[maxim].pop();
		int smaxim = 0;
		for (int i = 0; i < cur_stack; i++) {
			if (comp(smaxim, i) && i != maxim) {
				smaxim = i;
			}
			//cout << i << ": " << st[i].size() << endl;
		}
		int v2 = st[smaxim].top();
		st[smaxim].pop();
		res_mx[c] = v1;
		res_mx[v1] = v2;
		res_mx[v2] = c;
		useds[c] = useds[v2] = useds[v1] = true;
		for (int i = 0; i < cur_stack; i++) {
			while (!st[i].empty()) {
				st[i].pop();
			}
		}
	}
	int cur_stack = 0;
	for (int to : g[c]) {
		inch_tenum_es_qci_stacki_mej(to, c, cur_stack++);
	}
	int minim = cur_stack;
	if (!useds[c]) {
		st[minim].push(c);
		cur_stack++;
	}
	for (int i = 0; i < cur_stack; i++) {
		if(st[i].size()!=0)s.insert(i);
	}
	while (!s.empty()) {
		//cout << s.size() << endl;
		int bg = *s.rbegin();
		s.erase(--s.end());
		int sbg = *s.rbegin();
		s.erase(--s.end());
		int v1 = st[bg].top();
		int v2 = st[sbg].top();
		res_mx[v1] = v2;
		res_mx[v2] = v1;
		st[bg].pop();
		st[sbg].pop();
		if (st[bg].size() != 0) {
			s.insert(bg);
		}
		if (st[sbg].size() != 0) {
			s.insert(sbg);
		}
		//cout << bg << " " << sbg << endl;
	}
	cout << ans_mn << " " << ans_mx << endl;
	for (int v = 1; v <= n; v++) {
		cout << res_mn[v] << " ";
	}
	cout << endl;
	for (int v = 1; v <= n; v++) {
		cout << res_mx[v] << " ";
	}
	cout << endl;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Compilation message (stderr)

Village.cpp: In function 'void dfs(int, int)':
Village.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int i = 0; i < leaves.size() - 1; i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50