Submission #1248260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248260		pasta	Village (BOI20_village)	C++20	100 / 100	91 ms	39612 KiB

Village

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define pb	push_back
#define F   first
#define S   second
//#define int long long
const int maxn = 1e6 + 10;
const int LOG = 21;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

ll n, ret, ans, mn[maxn], sub[maxn], h[maxn], st[maxn];
vector<ll> G[maxn], res;

int clo = 0;
int dfs_sz(int v, int p) {
	sub[v] = 1;
	for (int u : G[v]) {
		if (u == p) continue;
		sub[v] += dfs_sz(u, v);
	}
	return sub[v];
}

int centroid(int v, int sz, int p) {
	for (int u : G[v]) {
		if (u == p) continue;
		if (sz < sub[u] * 2)
			return centroid(u, sz, v);
	}
	return v;
}

void dfs(int v, int p) {
	st[v] = clo++;
	res.pb(v);
	for (int u : G[v]) {
		if (u == p) continue;
		h[u] = h[v] + 1;
		ret += h[u];
		dfs(u, v);
	}
}

void dfs2(int v = 1, int p = 0){
    mn[v] = v;
    for (int u : G[v]) {
    	if (u == p) continue;
    	dfs2(u, v);
	}
	if (mn[v] == v) {
		ans += 2;
		if (p > 0) {
			swap(mn[v], mn[p]);
		}
		else {
			swap(mn[v], mn[G[v][0]]);
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		int v, u;
		cin >> v >> u;
		G[v].pb(u);
		G[u].pb(v);
	}
	int cen = centroid(1, dfs_sz(1, 0), 0);
	dfs(cen, 0);
	dfs2();
	cout << ans << ' ' << ret * 2 << '\n';
	for (int i = 1; i <= n; i++)
		cout << mn[i] << ' ';
	cout << '\n';
	for (int i = 1; i <= n; i++) {
		cout << res[(st[i] + n / 2)  % n] << ' ';
	}
	cout << '\n';
}

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