제출 #544753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544753		rainboy	Village (BOI20_village)	C11	100 / 100	110 ms	16748 KiB

Village

#include <stdio.h>
#include <stdlib.h>

#define N	100000

int *ej[N], eo[N], n;

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int jj[N], pp[N], dd[N], mn;

void match(int i) {
	while (dd[i] == 1) {
		int j = jj[i], tmp;

		if (pp[i] == i || dd[j] == 1)
			tmp = pp[i], pp[i] = pp[j], pp[j] = tmp;
		else
			mn -= 2;
		jj[i] ^= j, dd[i] = 0, jj[j] ^= i, dd[j]--;
		i = j;
	}
}

int sz[N], c;

void dfs1(int p, int i) {
	int o, centroid;

	sz[i] = 1, centroid = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs1(i, j);
			if (sz[j] * 2 > n)
				centroid = 0;
			sz[i] += sz[j];
		}
	}
	if ((n - sz[i]) * 2 > n)
		centroid = 0;
	if (centroid)
		c = i;
}

int qu[N], cnt; long long mx;

void dfs2(int p, int i, int d) {
	int o;

	mx += d * 2;
	qu[cnt++] = i;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs2(i, j, d + 1);
	}
}

int main() {
	static int qq[N];
	int h, i, j;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
		jj[i] ^= j, dd[i]++, jj[j] ^= i, dd[j]++;
	}
	for (i = 0; i < n; i++)
		pp[i] = i;
	mn = (n - 1) * 2;
	for (i = 0; i < n; i++)
		match(i);
	dfs1(-1, 0);
	dfs2(-1, c, 0);
	for (i = 0; i <= (n - 1) / 2; i++)
		qq[qu[i]] = qu[n / 2 + i], qq[qu[n / 2 + i]] = qu[i];
	if (n % 2 == 1)
		qq[qu[n - 1]] = qu[0];
	printf("%d %lld\n", mn, mx);
	for (i = 0; i < n; i++)
		printf("%d ", pp[i] + 1);
	printf("\n");
	for (i = 0; i < n; i++)
		printf("%d ", qq[i] + 1);
	printf("\n");
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Village.c: In function 'append':
Village.c:11:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   11 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Village.c: In function 'main':
Village.c:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Village.c:76:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

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