#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define N 6005
#define A 4000005
void pus(int **eh, int *eo, int i, int j) {
int o = eo[i]++;
if (!o) eh[i] = (int*)malloc(sizeof **eh * 2);
else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
eh[i][o] = j;
}
int ft[N];
void add(int p, int k) {
for (; p < N; p |= p + 1) ft[p] += k;
}
int sum(int p) {
int z = 0;
for (++p; p > 0; p &= p - 1) z += ft[p - 1];
return z;
}
int n_, s, n, m, k, m_, par[N], *eh[N], eo[N], dep[N],
ans[N], tin[N], tout[N], timer, *ph[A], po[A], *qh[A], qo[A], freq[A];
void dfs(int u) {
tin[u] = timer++;
for (int j = 0; j < eo[u]; ++j) dfs(eh[u][j]);
tout[u] = timer;
}
int main(void) {
scanf("%d%d%d%d", &n_, &m_, &k, &s);
n = n_ + m_;
++s;
for (int p, l, i = 1; i <= n; ++i) {
scanf("%d%d", &p, &l);
pus(eh, eo, par[i] = p, i);
dep[i] = dep[p] + l + 1;
}
dfs(0);
for (int i = n_ + 1; i <= n; ++i) {
ans[i] |= dep[i] == k;
for (int del = 1; del >= 0; --del) {
freq[dep[i]] = del;
for (int cur = i; cur != 0; cur = par[cur])
if (cur <= n_)
freq[dep[i]-dep[cur]] = del;
for (int j = 0; del == 1 && j <= n_; ++j)
if (k - s - dep[j] >= 0)
ans[i] |= freq[k - s - dep[j]];
}
if (k > dep[i])
pus(ph, po, k - dep[i], i);
}
for (int i = 0; i <= n_; ++i)
for (int j = 0; j <= n_; ++j)
if (tin[i] <= tin[j] && tout[j] <= tout[i] && s + dep[j] - dep[i] < A)
pus(qh, qo, s + dep[j] - dep[i], i);
for (int l = 1; l < A; ++l)
for (int del = 1; del >= -1; del -= 2) {
for (int low, j = 0; j < qo[l]; ++j)
add(tin[qh[l][j]], del),
add(tout[qh[l][j]], -del);
for (int ll = l; del == 1 && ll < A; ll += l)
for (int j = 0; j < po[ll]; ++j)
if (sum(tin[ph[ll][j]]) > 0)
ans[ph[ll][j]] = 1;
}
for (int i = n_ + 1; i <= n; ++i)
puts(ans[i] ? "YES": "NO");
}
Compilation message
fil.c: In function 'pus':
fil.c:11:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
11 | else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
| ~~^~~
fil.c: In function 'main':
fil.c:72:16: warning: unused variable 'low' [-Wunused-variable]
72 | for (int low, j = 0; j < qo[l]; ++j)
| ^~~
fil.c:35:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | scanf("%d%d%d%d", &n_, &m_, &k, &s);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.c:40:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d%d", &p, &l);
| ^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
71 ms |
4632 KB |
Output is correct |
2 |
Correct |
60 ms |
4776 KB |
Output is correct |
3 |
Correct |
70 ms |
7792 KB |
Output is correct |
4 |
Correct |
66 ms |
9052 KB |
Output is correct |
5 |
Correct |
69 ms |
30908 KB |
Output is correct |
6 |
Correct |
67 ms |
29272 KB |
Output is correct |
7 |
Correct |
77 ms |
33368 KB |
Output is correct |
8 |
Correct |
62 ms |
26712 KB |
Output is correct |
9 |
Correct |
63 ms |
27736 KB |
Output is correct |
10 |
Correct |
64 ms |
4596 KB |
Output is correct |
11 |
Correct |
60 ms |
6744 KB |
Output is correct |
12 |
Correct |
65 ms |
8280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
31068 KB |
Output is correct |
2 |
Correct |
100 ms |
30580 KB |
Output is correct |
3 |
Correct |
93 ms |
32576 KB |
Output is correct |
4 |
Correct |
83 ms |
30556 KB |
Output is correct |
5 |
Correct |
448 ms |
67296 KB |
Output is correct |
6 |
Correct |
436 ms |
70740 KB |
Output is correct |
7 |
Correct |
258 ms |
52376 KB |
Output is correct |
8 |
Correct |
267 ms |
53104 KB |
Output is correct |
9 |
Correct |
92 ms |
29644 KB |
Output is correct |
10 |
Correct |
83 ms |
30300 KB |
Output is correct |
11 |
Correct |
94 ms |
7812 KB |
Output is correct |
12 |
Correct |
338 ms |
41300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
71 ms |
4632 KB |
Output is correct |
2 |
Correct |
60 ms |
4776 KB |
Output is correct |
3 |
Correct |
70 ms |
7792 KB |
Output is correct |
4 |
Correct |
66 ms |
9052 KB |
Output is correct |
5 |
Correct |
69 ms |
30908 KB |
Output is correct |
6 |
Correct |
67 ms |
29272 KB |
Output is correct |
7 |
Correct |
77 ms |
33368 KB |
Output is correct |
8 |
Correct |
62 ms |
26712 KB |
Output is correct |
9 |
Correct |
63 ms |
27736 KB |
Output is correct |
10 |
Correct |
64 ms |
4596 KB |
Output is correct |
11 |
Correct |
60 ms |
6744 KB |
Output is correct |
12 |
Correct |
65 ms |
8280 KB |
Output is correct |
13 |
Correct |
81 ms |
31068 KB |
Output is correct |
14 |
Correct |
100 ms |
30580 KB |
Output is correct |
15 |
Correct |
93 ms |
32576 KB |
Output is correct |
16 |
Correct |
83 ms |
30556 KB |
Output is correct |
17 |
Correct |
448 ms |
67296 KB |
Output is correct |
18 |
Correct |
436 ms |
70740 KB |
Output is correct |
19 |
Correct |
258 ms |
52376 KB |
Output is correct |
20 |
Correct |
267 ms |
53104 KB |
Output is correct |
21 |
Correct |
92 ms |
29644 KB |
Output is correct |
22 |
Correct |
83 ms |
30300 KB |
Output is correct |
23 |
Correct |
94 ms |
7812 KB |
Output is correct |
24 |
Correct |
338 ms |
41300 KB |
Output is correct |
25 |
Correct |
79 ms |
29284 KB |
Output is correct |
26 |
Correct |
100 ms |
30548 KB |
Output is correct |
27 |
Correct |
81 ms |
31068 KB |
Output is correct |
28 |
Correct |
81 ms |
32604 KB |
Output is correct |
29 |
Correct |
439 ms |
69688 KB |
Output is correct |
30 |
Correct |
459 ms |
68748 KB |
Output is correct |
31 |
Correct |
262 ms |
53068 KB |
Output is correct |
32 |
Correct |
282 ms |
52684 KB |
Output is correct |
33 |
Correct |
102 ms |
30548 KB |
Output is correct |
34 |
Correct |
82 ms |
32092 KB |
Output is correct |
35 |
Correct |
79 ms |
7512 KB |
Output is correct |
36 |
Correct |
362 ms |
43076 KB |
Output is correct |