oj.uz

Submission #544764

# Submission time Handle Problem Language Result Execution time Memory
544764 2022-04-02T16:34:36 Z rainboy Link (CEOI06_link) C
100 / 100
 401 ms 54920 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 12 ms 3540 KB Output is correct
7 Correct 19 ms 4820 KB Output is correct
8 Correct 29 ms 7344 KB Output is correct
9 Correct 44 ms 15436 KB Output is correct
10 Correct 47 ms 11640 KB Output is correct
11 Correct 94 ms 33912 KB Output is correct
12 Correct 126 ms 15688 KB Output is correct
13 Correct 153 ms 30984 KB Output is correct
14 Correct 221 ms 30240 KB Output is correct
15 Correct 241 ms 40912 KB Output is correct
16 Correct 262 ms 45656 KB Output is correct
17 Correct 286 ms 48064 KB Output is correct
18 Correct 360 ms 44872 KB Output is correct
19 Correct 380 ms 47060 KB Output is correct
20 Correct 328 ms 49232 KB Output is correct
21 Correct 369 ms 54920 KB Output is correct
22 Correct 329 ms 52772 KB Output is correct
23 Correct 401 ms 52308 KB Output is correct
24 Correct 374 ms 52428 KB Output is correct
25 Correct 350 ms 51524 KB Output is correct