Submission #962837

#	Time	Username	Problem	Language	Result	Execution time	Memory
962837		josanneo22	Village (BOI20_village)	C++17	75 / 100	77 ms	20408 KiB

Village

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

const int nax = 200005;
int rep[nax], par[nax], N, sz[nax];
bool swp[nax];
vector<int> G[nax], tab, pos;

void dfs(int u, int f) {
	par[u] = f;
	tab.push_back(u);
	for (auto v : G[u]) {
		if (v == f) continue;
		dfs(v, u);
	}
}
pair<int, vector<int>> smallest() {
	for (int i = 1; i <= N; i++) {
		rep[i] = i;
		swp[i] = false;
		par[i] = -1;
	}
	dfs(1, -1);
	reverse(tab.begin(), tab.end());
	int ans = 0;
	for (auto u : tab) {
		if (swp[u] == false) {
			int v = par[u];
			if (v == -1) v = G[u][0];
			swp[u] = swp[v] = true;
			swap(rep[u], rep[v]);
			ans += 2;
		}
	}						 
	tab.clear();
	for (int i = 1; i <= N; i++) 
		pos.push_back(rep[i]);
	return { ans, pos };
}
i64 sum = 0;
void dfs_size(int u, int f) {
	tab.push_back(u);
	sz[u] = 1;
	for (auto v : G[u]) {
		if (v == f) continue;
		dfs_size(v, u);
		sz[u] += sz[v];
	}
	sum += 2LL * min(sz[u], (N - sz[u]));
}
int find_centroid(int u, int f) {
	for (auto v : G[u]) {
		if (v == f) continue;
		if (sz[v] > N / 2) 
			return find_centroid(v, u);
	}
	return u;
}
pair<int, vector<int>> largest() {
	dfs_size(1, -1);
	int root = find_centroid(1, -1);
	tab.clear(); pos.clear();
	sum = 0;
	dfs_size(root, -1);
	for (int i = 0; i < N; i++) 
		rep[tab[i]] = tab[(i + N / 2) % N];
	for (int i = 1; i <= N; i++)
		pos.push_back(rep[i]);
	return { sum, pos };
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N;
	for (int i = 1; i <= N - 1; i++) {
		int u, v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	auto A = smallest();
	auto B = largest();
	cout << A.first << ' ' << B.first << '\n';
	for (auto o : A.second) cout << o << " \n"[o == A.second.back()];
	for (auto o : B.second) cout << o << " \n"[o == B.second.back()];
}

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