#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--;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
