Submission #291665

#	Time	Username	Problem	Language	Result	Execution time	Memory
291665		spdskatr	Village (BOI20_village)	C++14	100 / 100	196 ms	34248 KiB

Village

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

int N, dp[100005][2], ans[100005], conn[100005], seen[100005]; // 0 = isolated, 1 = attached
vector<int> graph[100005], g2[100005];
vector<int> broken[100005], unbroken[100005];
vector<int> order;

int sz[100005], ans2[100005];
long long tot;
vector<int> nds;

void dfs(int x, int p) {
	dp[x][1] = 0;
	int mindiff = 2069696969;
	for (int v : graph[x]) {
		if (v != p) {
			dfs(v, x);
			int df = max(0, dp[v][0] + 1 - dp[v][1]);
			if (mindiff > df) {
				mindiff = df;
				conn[x] = v;
			}
			if (dp[v][0] + 1 > dp[v][1]) {
				broken[x].push_back(v);
				dp[x][1] += dp[v][0] + 1;
			} else {
				unbroken[x].push_back(v);
				dp[x][1] += dp[v][1];
			}
		}
	}
	dp[x][0] = dp[x][1] - mindiff;
}

void dfs2(int x, int state) {
	int keep = -1;
	if (state == 0) {
		keep = conn[x];
	}
	if (keep != -1) {
		g2[x].push_back(keep);
		g2[keep].push_back(x);
		dfs2(keep, 1);
	}
	for (int v : broken[x]) {
		if (v != keep) {
			dfs2(v, 0);
		}
	}
	for (int v : unbroken[x]) {
		if (v != keep) {
			g2[x].push_back(v);
			g2[v].push_back(x);
			dfs2(v, 1);
		}
	}
}

void dfs3(int x, int p) {
	seen[x] = 1;
	order.push_back(x);
	for (int v : g2[x]) if (v != p) dfs3(v, x);
}

void dfs4(int x, int p) {
	sz[x] = 1;
	for (int v : graph[x]) if (v != p) {
		dfs4(v, x);
		tot += min(sz[v], N - sz[v]);
		sz[x] += sz[v];
	}
}

void dfs5(int x, int p) {
	nds.push_back(x);
	for (int v : graph[x]) if (v != p) dfs5(v, x);
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N-1; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	dfs(1, 1);
	dfs2(1, 0); // Create g2
	for (int i = 1; i <= N; i++) {
		if (!seen[i]) {
			order.clear();
			dfs3(i, i);
			for (int j = 0; j < order.size(); j++) {
				ans[order[j]] = order[(j+1)%order.size()];
			}
		}
	}
	// Find centroid
	dfs4(1, 1);
	int cent = 1, rip = 1;
	while (rip) {
		rip = 0;
		for (int v : graph[cent]) {
			if (sz[v] < sz[cent] && sz[v] > (sz[1] / 2)) {
				rip = 1;
				cent = v;
				break;
			}
		}
	}	
	// Cent is centroid
	for (int v : graph[cent]) {
		dfs5(v, cent);
	}
	if (nds.size() & 1) {
		nds.push_back(cent);
		int of = nds.size() / 2;
		for (int i = 0; i + of < nds.size(); i++) {
			ans2[nds[i]] = nds[i + of];
			ans2[nds[i+of]] = nds[i];
		}
	} else {
		int of = nds.size() / 2;
		ans2[nds[0]] = cent;
		ans2[cent] = nds[of];
		ans2[nds[of]] = nds[0];
		for (int i = 1; i + of < nds.size(); i++) {
			ans2[nds[i]] = nds[i+of];
			ans2[nds[i+of]] = nds[i];
		}
	}
	printf("%d %lld\n", 2 * (N-1-dp[1][0]), 2 * tot);
	for (int i = 1; i <= N; i++) {
		if (i == 1) printf("%d", ans[i]);
		else printf(" %d", ans[i]);
	} printf("\n");
	for (int i = 1; i <= N; i++) {
		if (i == 1) printf("%d", ans2[i]);
		else printf(" %d", ans2[i]);
	} printf("\n");
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |    for (int j = 0; j < order.size(); j++) {
      |                    ~~^~~~~~~~~~~~~~
Village.cpp:123:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for (int i = 0; i + of < nds.size(); i++) {
      |                   ~~~~~~~^~~~~~~~~~~~
Village.cpp:132:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for (int i = 1; i + of < nds.size(); i++) {
      |                   ~~~~~~~^~~~~~~~~~~~
Village.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Village.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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