Submission #670850

#	Time	Username	Problem	Language	Result	Execution time	Memory
670850		rainboy	Capital City (JOI20_capital_city)	C11	11 / 100	352 ms	365024 KiB

capital_city

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

#define N	200000
#define L	18	/* L = ceil(log2(N)) */
#define N_	(N + N * (L + 1))

int min(int a, int b) { return a < b ? a : b; }

int *ej[N], eo[N], *ej_[N], eo_[N], *fi_[N], fo_[N], n, k;
int aa[N];

void append(int **ej, int *eo, 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;
}

void add_edge(int i, int j) {
	append(ej_, eo_, i, j), append(fi_, fo_, j, i);
}

int dd[N], pp[N][L + 1], qu[N_], cnt;

void dfs0(int p, int i, int d) {
	int o, l, q;

	qu[cnt++] = i;
	dd[i] = d, pp[i][0] = q = p;
	add_edge(k + i * (L + 1) + 0, aa[i]);
	for (l = 1; l <= L; l++)
		if (q == -1) {
			pp[i][l] = -1;
			add_edge(k + i * (L + 1) + l, k + i * (L + 1) + l - 1);
		} else {
			pp[i][l] = pp[q][l - 1];
			add_edge(k + i * (L + 1) + l, k + i * (L + 1) + l - 1);
			add_edge(k + i * (L + 1) + l, k + q * (L + 1) + l - 1);
			q = pp[i][l];
		}
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

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

int cc[N_]; char out[N_];

void dfs1(int i) {
	int o;

	if (cc[i])
		return;
	cc[i] = -1;
	for (o = eo_[i]; o--; ) {
		int j = ej_[i][o];

		dfs1(j);
	}
	qu[--cnt] = i;
}

void dfs2(int j, int c) {
	int o;

	if (cc[j] != -1) {
		if (cc[j] != c)
			out[cc[j]] = 1;
		return;
	}
	cc[j] = c;
	for (o = fo_[j]; o--; ) {
		int i = fi_[j][o];

		dfs2(i, c);
	}
}

void add_path(int i, int j, int u) {
	int l, tmp;

	if (dd[i] < dd[j])
		tmp = i, i = j, j = tmp;
	for (l = L; l >= 0; l--)
		if (dd[i] - dd[j] >= 1 << l)
			add_edge(u, k + i * (L + 1) + l), i = pp[i][l];
	if (i == j)
		add_edge(u, k + i * (L + 1) + 0);
	else {
		for (l = L; l >= 0; l--)
			if (dd[i] >= 1 << l && pp[i][l] != pp[j][l]) {
				add_edge(u, k + i * (L + 1) + l), i = pp[i][l];
				add_edge(u, k + j * (L + 1) + l), j = pp[j][l];
			}
		add_edge(u, k + i * (L + 1) + 1);
		add_edge(u, k + j * (L + 1) + 1);
	}
}

int main() {
	static int kk[N_], prev[N];
	int n_, h, i, j, a, c, ans;

	scanf("%d%d", &n, &k);
	n_ = k + n * (L + 1);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (i = 0; i < n_; i++) {
		ej_[i] = (int *) malloc(2 * sizeof *ej_[i]);
		fi_[i] = (int *) malloc(2 * sizeof *fi_[i]);
	}
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(ej, eo, i, j), append(ej, eo, j, i);
	}
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]), aa[i]--;
	dfs0(-1, 0, 0);
	memset(prev, -1, k * sizeof *prev);
	for (h = 0; h < cnt; h++) {
		j = qu[h], a = aa[j];
		prev[a] = j;
	}
	for (h = 0; h < cnt; h++) {
		j = qu[h], a = aa[j], i = prev[a];
		add_path(i, j, a);
		prev[a] = j;
	}
	cnt = n_;
	for (i = 0; i < n_; i++)
		dfs1(i);
	for (h = 0, c = 0; h < n_; h++) {
		i = qu[h];
		if (cc[i] == -1)
			dfs2(i, c++);
	}
	for (a = 0; a < k; a++)
		kk[cc[a]]++;
	ans = k + 1;
	for (a = 0; a < k; a++)
		if (!out[cc[a]])
		ans = min(ans, kk[cc[a]] - 1);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59