Submission #536337

#	Time	Username	Problem	Language	Result	Execution time	Memory
536337		skittles1412	Village (BOI20_village)	C++17	100 / 100	296 ms	40400 KiB

Village

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 1e5 + 5;

vector<int> graph[maxn];

void pdfs(int u) {
	for (auto& v : graph[u]) {
		graph[v].erase(find(begin(graph[v]), end(graph[v]), u));
		pdfs(v);
	}
}

namespace minv {

int memo[maxn][2];
vector<int> res, choice[maxn][2];

int dp(int u, bool b) {
	int& ans = memo[u][b];
	if (ans != -1) {
		return ans;
	}
	int m = sz(graph[u]);
	int cdp[m + 1][2], from[m + 1][2];
	memset(cdp, 0x3f, sizeof(cdp));
	cdp[0][0] = 0;
	for (int k = 0; k < m; k++) {
		int v = graph[u][k];
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				int cv = cdp[k][i] + dp(v, j) + (j ? 2 : 0);
				if (cv < cdp[k + 1][i || j]) {
					cdp[k + 1][i || j] = cv;
					from[k + 1][i || j] = (i << 1) | j;
				}
			}
		}
	}
	int j = 1;
	if (b) {
		if (cdp[m][0] < cdp[m][1]) {
			j = 0;
		}
	}
	ans = cdp[m][j];
	auto& c = choice[u][b];
	for (int i = m; i >= 1; i--) {
		int ci = from[i][j] >> 1, cj = from[i][j] & 1;
		c.push_back(cj);
		j = ci;
	}
	reverse(begin(c), end(c));
	return ans;
}

void cdp(int u, bool b) {
	int m = sz(graph[u]);
	for (int i = 0; i < m; i++) {
		int v = graph[u][i];
		if (choice[u][b][i]) {
			swap(res[u], res[v]);
			cdp(v, true);
		} else {
			cdp(v, false);
		}
	}
}

pair<int, vector<int>> solve(int n) {
	memset(memo, -1, sizeof(memo));
	dp(0, false);
	res = vector<int>(n);
	iota(begin(res), end(res), 0);
	cdp(0, false);
	return {dp(0, false), res};
}

}  // namespace minv

namespace maxv {

long ans = 0;
int n, siz[maxn];
bool cans, vis[maxn];
vector<int> res, comp;

void dfs1(int u, int p = -1) {
	if (vis[u]) {
		siz[u] = 0;
		return;
	}
	siz[u] = 1;
	for (auto& v : graph[u]) {
		if (v != p) {
			dfs1(v, u);
			siz[u] += siz[v];
			if (cans) {
				ans += min(siz[v], n - siz[v]);
			}
		}
	}
}

void dfs2(int u) {
	if (vis[u]) {
		return;
	}
	vis[u] = true;
	comp.push_back(u);
	for (auto& v : graph[u]) {
		dfs2(v);
	}
}

int centroid(int u) {
	while (true) {
		pair<int, int> opt {0, 0};
		for (auto& v : graph[u]) {
			opt = max(opt, pair<int, int> {siz[v], v});
		}
		if (opt.first > n / 2) {
			int v = opt.second;
			siz[u] -= siz[v];
			siz[v] += siz[u];
			u = v;
		} else {
			break;
		}
	}
	return u;
}

pair<long, vector<int>> solve(int _n) {
	n = _n;
	res = vector<int>(n);
	cans = true;
	dfs1(0);
	cans = false;
	int c = centroid(0);
	dbg(c);
	vector<vector<int>> groups;
	groups.push_back({c});
	vis[c] = true;
	for (auto& v : graph[c]) {
		comp.clear();
		dfs2(v);
		groups.push_back(comp);
	}
	sort(begin(groups), end(groups), [&](const auto &a, const auto &b) -> bool {
		return sz(a) > sz(b);
	});
	int m = sz(groups);
	vector<int> ngroups[m];
	for (int i = 0; i < m; i++) {
		dbg(sz(groups[i]));
		int j = i + 1;
		if (j == m) {
			j = 0;
		}
		for (auto& a : groups[i]) {
			while (sz(ngroups[j]) == sz(groups[j])) {
				j++;
				if (j == m) {
					j = 0;
				}
			}
			assert(i != j);
			ngroups[j].push_back(a);
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < sz(groups[i]); j++) {
			res[groups[i][j]] = ngroups[i][j];
		}
	}
	return {ans * 2, res};
}

}  // namespace maxv

void solve() {
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	auto [mx, mxa] = maxv::solve(n);
	pdfs(0);
	auto [mn, mna] = minv::solve(n);
	cout << mn << " " << mx << endl;
	for (int i = 0; i < n; i++) {
		cout << mna[i] + 1 << " \n"[i == n - 1];
	}
	for (int i = 0; i < n; i++) {
		cout << mxa[i] + 1 << " \n"[i == n - 1];
	}
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

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