제출 #1094481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094481		mat_jur	Village (BOI20_village)	C++17	100 / 100	69 ms	17504 KiB

Village

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

void dfs(int v, int p, vector<int> &match, const vector<vector<int>> &g) {
	for (int u : g[v]) {
		if (u == p) continue;
		dfs(u, v, match, g);
	}

	if (match[v] != -1) return;

	for (int u : g[v]) {
		if (match[u] == -1) {
			match[v] = u;
			match[u] = v;
		}
	}
}

vector<int> matching(const vector<vector<int>> &g) {
	int n = ssize(g);
	vector<int> match(n, -1);

	dfs(0, -1, match, g);

	return match;
}

void dfs_cent(int v, int p, vector<int> &s, const vector<vector<int>> &g) {
	s[v] = 1;
	for (int u : g[v]) {
		if (u == p) continue;
		dfs_cent(u, v, s, g);
		s[v] += s[u];
	}
}

int centroid(const vector<vector<int>> &g) {
	int n = ssize(g);
	vector<int> s(n);

	dfs_cent(0, -1, s, g);

//	debug(s);
	
	int c = 0;
	int p = -1;

	bool is_centroid = false;

	while (!is_centroid) {
		is_centroid = true;
		for (int u : g[c]) {
			if (u == p) continue;
			if (s[u] > n/2) {
				p = c;
				c = u;
				is_centroid = false;
				break;
			}
		}
	}

	return c;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;
	vector<vector<int>> g(n);

	for (int i = 0; i < n-1; ++i) {
		int u, v;
		cin >> u >> v;
		g[u-1].eb(v-1);
		g[v-1].eb(u-1);
	}

	vector<int> match = matching(g);

	int mn = n;

	for (int v = 0; v < n; ++v) {
		if (match[v] != -1) continue;
		mn++;
		int u = g[v][0];
		match[v] = match[u];
		match[u] = v;
	}

	int c = centroid(g);

	vector<int> match_mx(n, -1);

	vector<vector<int>> sub(ssize(g[c]));
	ll mx = 0;

	vector<int> dist(n);
	function<void(int, int, int)> add_sub = [&](int v, int p, int idx) {
		mx += dist[v];
		sub[idx].eb(v);
		for (int u : g[v]) {
			if (u == p) continue;
			dist[u] = dist[v] + 1;
			add_sub(u, v, idx);
		}
	};


	for (int i = 0; i < ssize(g[c]); ++i) {
		dist[g[c][i]] = 1;
		add_sub(g[c][i], c, i);
	}

	debug(c);

	debug(sub);

	sort(all(sub), [&](const vector<int> &a, const vector<int> &b) {
		return ssize(a) > ssize(b);
	});

	if (n%2 == 0) {
		int u = sub[0].back();
		sub[0].pop_back();
		int i = 0;
		while (i+1 < ssize(sub) && ssize(sub[i]) < ssize(sub[i+1])) {
			swap(sub[i], sub[i+1]);
			++i;
		}
		match_mx[c] = u;
		match_mx[u] = c;
	}

	debug(sub);

	priority_queue<pair<int, int>> q;
	for (int i = 0; i < ssize(sub); ++i) {
		if (ssize(sub[i])) q.push(mp(ssize(sub[i]), i));
	}

	while (ssize(q)) {
		debug(sub);
		debug(q.top());
		int a = q.top().se;
		q.pop();
		debug(q.top());
		int b = q.top().se;
		q.pop();
		int u = sub[a].back(), v = sub[b].back();
		match_mx[u] = v;
		match_mx[v] = u;
		sub[a].pop_back(); sub[b].pop_back();
		if (ssize(sub[a])) q.push(mp(ssize(sub[a]), a));
		if (ssize(sub[b])) q.push(mp(ssize(sub[b]), b));
	}
	
	if (n%2 == 1) {
		int u = g[c][0];
		match_mx[c] = match_mx[u];
		match_mx[u] = c;
	}

//	debug(match_mx);
	cout << mn << ' ' << 2*mx << '\n';
	for (int x : match) cout << x+1 << ' ';
	cout << '\n';
	for (int x : match_mx) cout << x+1 << ' ';
	cout << '\n';

	/*for (int i = 0; i < n; ++i) {
		if (match_mx[i] == -1) {
			cout << "WA";
			return 0;	
		}
	}

	cout << "OK";*/
	
	return 0;
}

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