Submission #286327

#	Time	Username	Problem	Language	Result	Execution time	Memory
286327		spdskatr	Village (BOI20_village)	C++14	50 / 100	164 ms	34040 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;

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;
	//printf("dp[%d][0]: %d\ndp[%d][1]: %d\n", x, dp[x][0], x, dp[x][1]);
}

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);
		//printf("edge %d - %d added\n", x, keep);
		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);
			//printf("edge %d - %d added\n", x, v);
			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);
}

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()];
			}
		}
	}
	printf("%d 69\n", 2 * (N-1-dp[1][0]));
	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", ans[i]);
		else printf(" %d", ans[i]);
	} printf("\n");
}

Compilation message (stderr)

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

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