Submission #806729

#	Time	Username	Problem	Language	Result	Execution time	Memory
806729		pawned	Village (BOI20_village)	C++17	56 / 100	100 ms	16136 KiB

Village

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

int N;

vector<ii> edges;
vi adj[100005];

pair<int, vi> minimumans;

void bruteforce() {

	vector<vi> dist(N, vi(N, 1e9));
	for (int i = 0; i < N; i++) {	// starting node
		queue<int> q;
		dist[i][i] = 0;
		q.push(i);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (int j : adj[x]) {
				if (dist[i][j] == 1e9) {
					dist[i][j] = dist[i][x] + 1;
					q.push(j);
				}
			}
		}
	}
/*
	cout<<"dist: "<<endl;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout<<dist[i][j]<<" ";
		}
		cout<<endl;
	}
*/
	vi perm(N);
	for (int i = 0; i < N; i++) {
		perm[i] = i;
	}
	int minimum = 1e9;
	vi minans;
	int maximum = 0;
	vi maxans;
	int count = 0;
	do {
		bool can = true;
		for (int i = 0; i < N; i++) {
			if (perm[i] == i)
				can = false;
		}
		if (!can)
			continue;
		count++;
		int total = 0;
		for (int i = 0; i < N; i++) {
			total += dist[i][perm[i]];
		}
		if (total < minimum) {
			minimum = total;
			minans = perm;
		}
		if (total > maximum) {
			maximum = total;
			maxans = perm;
		}
	} while (next_permutation(perm.begin(), perm.begin() + N));
//	cout<<"count: "<<count<<endl;
/*
	cout<<minimum<<" "<<maximum<<endl;
	for (int i = 0; i < N; i++) {
		cout<<(minans[i] + 1)<<" ";
	}
	cout<<endl;
	for (int i = 0; i < N; i++) {
		cout<<(maxans[i] + 1)<<" ";
	}
	cout<<endl;
*/
	minimumans.fi = minimum;
	minimumans.se = minans;
}

int subtree_size[100005];

bool vis[100005];

void dfs(int n) {
	vis[n] = true;
	subtree_size[n] = 1;
	for (int i : adj[n]) {
		if (!vis[i]) {
			dfs(i);
			subtree_size[n] += subtree_size[i];
		}
	}
}

bool vis2[100005];

int dfs2(int n) {
//	cout<<"at "<<n<<endl;
	vis2[n] = true;
	bool works = true;
	for (int i : adj[n]) {
		if (!vis2[i]) {
			if (subtree_size[i] > N / 2) {
				works = false;
				return dfs2(i);
			}
		}
	}
	if (works) {
//		cout<<"yay "<<n<<endl;
		return n;
	}
	return -1;
}

vi order;

bool vis3[100005];

void dfs3(int n) {
	vis3[n] = true;
	order.pb(n);
	for (int i : adj[n]) {
		if (!vis3[i]) {
			dfs3(i);
		}
	}
}

int main() {
	cin>>N;
	for (int i = 0; i < N - 1; i++) {
		int u, v;
		cin>>u>>v;
		u--; v--;
		edges.pb({u, v});
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(0);
/*
	cout<<"subtree size: ";
	for (int i = 0; i < N; i++) {
		cout<<subtree_size[i]<<" ";
	}
	cout<<endl;
*/
	ll total = 0;
	for (int i = 0; i < N - 1; i++) {
		int u = edges[i].fi;
		int v = edges[i].se;
		if (subtree_size[u] < subtree_size[v])	// u is parent of v
			swap(u, v);
		total += min(subtree_size[v], N - subtree_size[v]);
	}
	total *= 2;
	int centroid = dfs2(0);	// find centroid
//	cout<<"centroid: "<<centroid<<endl;
	dfs3(centroid);	// need order
/*
	cout<<"order: ";
	for (int i : order)
		cout<<i<<" ";
	cout<<endl;
*/
	int ans[N];
	if (N % 2 == 0) {
		for (int i = 0; i < N / 2; i++) {
			ans[order[i]] = order[i + N / 2];
			ans[order[i + N / 2]] = order[i];
		}
	}
	else {
		ans[order[0]] = order[0];
		for (int i = 0; i < N / 2; i++) {
			ans[order[i + 1]] = order[i + N / 2 + 1];
			ans[order[i + N / 2 + 1]] = order[i + 1];
		}
		swap(ans[order[0]], ans[order[1]]);
	}
//	cout<<"ANSWER: "<<endl;
	if (N <= 10) {
		bruteforce();
	}
	else {
		minimumans.fi = 0;
		minimumans.se = vi(N, 1);
	}
	cout<<minimumans.fi<<" "<<total<<endl;
	for (int i = 0; i < N; i++) {
		cout<<(minimumans.se[i] + 1)<<" ";
	}
	cout<<endl;
	for (int i = 0; i < N; i++) {
		cout<<(ans[i] + 1)<<" ";
	}
	cout<<endl;
}

// find centroid, do dfs order, then map i to i + N / 2
// only important is that start and end never belong to same tree
// n = 8: (1, 2, 3, 4) <=> (5, 6, 7, 8)
// n = 9: (2, 3, 4, 5) <=> (6, 7, 8, 9), then swap the "goto" for
// 1 and 2 (then 1 -> 1 and 2 -> 6 becomes 1 -> 6 and 2 -> 1)

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