Submission #544764

#	Time	Username	Problem	Language	Result	Execution time	Memory
544764		rainboy	Link (CEOI06_link)	C11	100 / 100	401 ms	54920 KiB

link

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

#define N	500000
#define L	19	/* L = ceil(log2(N)) */
#define INF	0x3f3f3f3f

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

int *ej[N], eo[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 dp[N], dq[N], k;

void dfs(int i) {
	int o, p, q;

	p = 0, q = i == 0 ? k + 1 : 0;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(j);
		p += dp[j], q = max(q, dq[j]);
	}
	if (q == 0)
		p++, q = k;
	dp[i] = p, dq[i] = q - 1;
}

int solve(int *aa, int n) {
	static int pp[L + 1][N * 2 + 1];
	int i, j, l, ans;

	for (i = n + n, j = n + n; i >= 0; i--) {
		if (i + k < n + n && aa[(i + k) % n] == 1)
			j = i + k;
		pp[0][i] = j;
	}
	for (l = 0; l < L; l++)
		for (i = 0; i <= n + n; i++)
			pp[l + 1][i] = pp[l][pp[l][i]];
	ans = INF;
	for (i = 0; i < n; i++) {
		int cnt;

		j = i, cnt = 0;
		for (l = L; l >= 0; l--)
			if (pp[l][j] < i + n)
				j = pp[l][j], cnt += 1 << l;
		cnt++;
		ans = min(ans, cnt);
	}
	return ans;
}

int main() {
	static int pp[N], dd[N], aa[N];
	static char cc[N];
	int n, h, i, j, ans;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n; h++) {
		int p;

		scanf("%d%d", &i, &p), i--, p--;
		append(p, i);
		pp[i] = p;
	}
	for (i = 0; i < n; i++)
		if (!cc[i]) {
			for (j = i; !cc[j]; j = pp[j])
				cc[j] = -2;
			if (cc[j] == -2)
				for ( ; cc[j] == -2; j = pp[j])
					cc[j] = -1;
			for (j = i; cc[j] == -2; j = pp[j])
				cc[j] = 1;
		}
	ans = 0;
	for (i = 0; i < n; i++)
		if (cc[i] == -1) {
			int o;

			if (i == 0)
				dd[i] = k + 1;
			for (o = eo[i]; o--; ) {
				j = ej[i][o];
				if (cc[j] != -1) {
					dfs(j);
					ans += dp[j];
					dd[i] = max(dd[i], dq[j]);
				}
			}
		}
	for (i = 0; i < n; i++)
		if (cc[i] == -1) {
			int cnt, zero;

			j = i;
			do
				dd[pp[j]] = max(dd[pp[j]], dd[j] - 1), j = pp[j];
			while (j != i);
			j = i, cnt = 0, zero = 1;
			do {
				if ((aa[cnt++] = dd[j] == 0) == 1)
					zero = 0;
				cc[j] = -2, dd[pp[j]] = max(dd[pp[j]], dd[j] - 1), j = pp[j];
			} while (j != i);
			ans += zero ? 0 : solve(aa, cnt);
		}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100