Submission #916517

#	Time	Username	Problem	Language	Result	Execution time	Memory
916517		NK_	Village (BOI20_village)	C++17	100 / 100	67 ms	19312 KiB

Village

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	V<vi> adj(N); for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	vi sub(N); function<void(int, int)> gen = [&](int u, int p) {
		sub[u] = 1;
		for(auto& v : adj[u]) if (v != p) {
			gen(v, u); sub[u] += sub[v];
		}
	};

	function<int(int, int)> find = [&](int u, int p) {
		for(auto& v : adj[u]) if (v != p) {
			if (2 * sub[v] >= N) return find(v, u);
		}

		return u;
	};

	gen(0, -1); int R = find(0, -1);

	// cout << R << endl;

	ll lans = 0, gans = 0;
	vi L(N), G(N); iota(begin(L), end(L), 0);

	vi ord;
	function<int(int, int)> answer = [&](int u, int p) {
		ord.pb(u); sub[u] = 1;

		vi chd = {u};
		for(auto& v : adj[u]) if (v != p) {
			int r = answer(v, u); 
			sub[u] += sub[v];
			gans += 2 * sub[v];
			if (r != -1) chd.pb(r);
		}


		if (sz(chd) == 1) {
			lans += 2;
			return chd[0];
		}

		for(int i = 0; i < sz(chd); i++) {
			int j = (i + 1) % sz(chd);
			L[chd[j]] = chd[i];
		}

		return -1;
	};

	int r = answer(R, -1);
	if (r != -1) {
		for(auto& v : adj[R]) {
			swap(L[R], L[v]);
			break;
		}
	}

	int mx = 0;
	for(auto& v : adj[R]) mx = max(mx, sub[v]);

	for(int x = 0; x < N; x++) {
		int y = (x + mx) % N;
		G[ord[y]] = ord[x];
	}

	cout << lans << " " << gans << nl;
	
	for(auto& x : L) cout << x + 1 << " ";
	cout << nl;

	for(auto& x : G) cout << x + 1 << " ";
	cout << nl;





	exit(0-0);
}

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