Submission #723092

#	Time	Username	Problem	Language	Result	Execution time	Memory
723092		gagik_2007	Village (BOI20_village)	C++17	56 / 100	81 ms	22604 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;
ll ans_mn = 0;
bool used[N];
int dist[LG][LG];

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_dist(int v, int par, int cur, int u) {
	dist[u][v] = cur;
	for (int to : g[v]) {
		if (to != par) {
			calc_dist(to, v, cur + 1, u);
		}
	}
}

int main() {
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	if (n <= 10) {
		vector<int>p;
		for (int v = 1; v <= n; v++) {
			p.push_back(v);
			calc_dist(v, v, 0, v);
		}
		vector<int>mx, mn;
		int mxv = 0, mnv = MOD;
		do {
			int cur_sz = 0;
			bool ok = true;
			for (int v = 1; v <= n; v++) {
				cur_sz += dist[v][p[v - 1]];
				if (p[v - 1] == v) {
					ok = false;
				}
			}
			if (ok) {
				if (cur_sz > mxv) {
					mxv = cur_sz;
					mx = p;
				}
				if (cur_sz < mnv) {
					mnv = cur_sz;
					mn = p;
				}
			}
		} while (next_permutation(p.begin(), p.end()));
		cout << mnv << " " << mxv << endl;
		for (int x : mn) {
			cout << x << " ";
		}
		cout << endl;
		for (int x : mx) {
			cout << x << " ";
		}
		cout << endl;
		return 0;
	}
	int leaf = 0;
	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);
	dfs(root);
	cout << ans_mn << " ";
	cout << ans_mn << endl;
	for (int v = 1; v <= n; v++) {
		cout << res_mn[v] << " ";
	}
	cout << endl;
	for (int v = 1; v <= n; v++) {
		cout << res_mn[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:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int i = 0; i < leaves.size() - 1; i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~

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