Submission #806715

#	Time	Username	Problem	Language	Result	Execution time	Memory
806715		pawned	Village (BOI20_village)	C++17	0 / 100	2 ms	2660 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];

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;
	cout<<0<<endl;
	for (int i = 0; i < N; i++) {
		cout<<1<<" ";
	}
	cout<<endl;
	cout<<total<<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: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50