#include <stdio.h>
#include <stdlib.h>
#define N 300000
#define INF 0x3f3f3f3f3f3f3f3fLL
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
int *ej[N], *ew[N], eo[N];
void append(int i, int j, int w) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0) {
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
}
ej[i][o] = j, ew[i][o] = w;
}
long long dp[N], dq[N], d; int qu[N], cnt;
void dfs(int p, int i) {
int o;
dp[i] = -1, dq[i] = INF;
for (o = eo[i]; o--; ) {
int j = ej[i][o], w = ew[i][o];
if (j != p) {
dfs(i, j);
if (dp[j] != -1) {
if (dp[j] + w > d)
qu[cnt++] = j, dq[j] = 0;
else
dp[i] = max(dp[i], dp[j] + w);
}
dq[i] = min(dq[i], dq[j] + w);
}
}
if (dp[i] != -1 && dp[i] + dq[i] <= d)
dp[i] = -1;
if (dq[i] > d)
dp[i] = max(dp[i], 0);
}
int main() {
int n, h, i, j, w;
scanf("%d%lld", &n, &d);
for (i = 0; i < n; i++) {
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
ew[i] = (int *) malloc(2 * sizeof *ew[i]);
}
for (h = 0; h < n - 1; h++) {
scanf("%d%d%d", &i, &j, &w), i--, j--;
append(i, j, w), append(j, i, w);
}
dfs(-1, 0);
if (dp[0] != -1)
qu[cnt++] = 0;
printf("%d\n", cnt);
while (cnt--)
printf("%d ", qu[cnt] + 1);
printf("\n");
return 0;
}
Compilation message
Firefighting.c: In function 'append':
Firefighting.c:15:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
15 | if (o >= 2 && (o & o - 1) == 0) {
| ~~^~~
Firefighting.c: In function 'main':
Firefighting.c:51:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d%lld", &n, &d);
| ^~~~~~~~~~~~~~~~~~~~~~~
Firefighting.c:57:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d%d%d", &i, &j, &w), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
226 ms |
39908 KB |
Output is correct |
2 |
Correct |
220 ms |
39904 KB |
Output is correct |
3 |
Correct |
62 ms |
14924 KB |
Output is correct |
4 |
Correct |
227 ms |
38840 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
288 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
292 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
296 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
292 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
292 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
296 KB |
Output is correct |
14 |
Correct |
0 ms |
296 KB |
Output is correct |
15 |
Correct |
0 ms |
300 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
226 ms |
39904 KB |
Output is correct |
2 |
Correct |
86 ms |
20632 KB |
Output is correct |
3 |
Correct |
106 ms |
21440 KB |
Output is correct |
4 |
Correct |
77 ms |
18412 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
192 ms |
37356 KB |
Output is correct |
8 |
Correct |
173 ms |
37200 KB |
Output is correct |
9 |
Correct |
169 ms |
37324 KB |
Output is correct |
10 |
Correct |
177 ms |
37360 KB |
Output is correct |
11 |
Correct |
224 ms |
39908 KB |
Output is correct |
12 |
Correct |
141 ms |
25080 KB |
Output is correct |
13 |
Correct |
65 ms |
15880 KB |
Output is correct |
14 |
Correct |
118 ms |
23804 KB |
Output is correct |
15 |
Correct |
140 ms |
28952 KB |
Output is correct |
16 |
Correct |
182 ms |
31004 KB |
Output is correct |
17 |
Correct |
125 ms |
26204 KB |
Output is correct |
18 |
Correct |
136 ms |
25688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
564 KB |
Output is correct |
3 |
Correct |
1 ms |
436 KB |
Output is correct |
4 |
Correct |
1 ms |
436 KB |
Output is correct |
5 |
Correct |
1 ms |
692 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
724 KB |
Output is correct |
14 |
Correct |
2 ms |
692 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
496 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
536 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
35468 KB |
Output is correct |
2 |
Correct |
201 ms |
33872 KB |
Output is correct |
3 |
Correct |
195 ms |
36576 KB |
Output is correct |
4 |
Correct |
76 ms |
17092 KB |
Output is correct |
5 |
Correct |
205 ms |
44060 KB |
Output is correct |
6 |
Correct |
212 ms |
42856 KB |
Output is correct |
7 |
Correct |
219 ms |
46512 KB |
Output is correct |
8 |
Correct |
199 ms |
45644 KB |
Output is correct |
9 |
Correct |
221 ms |
41664 KB |
Output is correct |
10 |
Correct |
237 ms |
41016 KB |
Output is correct |
11 |
Correct |
228 ms |
48492 KB |
Output is correct |
12 |
Correct |
148 ms |
24736 KB |
Output is correct |
13 |
Correct |
200 ms |
42588 KB |
Output is correct |
14 |
Correct |
229 ms |
40416 KB |
Output is correct |
15 |
Correct |
268 ms |
36828 KB |
Output is correct |
16 |
Correct |
187 ms |
34628 KB |
Output is correct |
17 |
Correct |
187 ms |
34180 KB |
Output is correct |
18 |
Correct |
189 ms |
36748 KB |
Output is correct |
19 |
Correct |
129 ms |
25768 KB |
Output is correct |
20 |
Correct |
50 ms |
14784 KB |
Output is correct |
21 |
Correct |
193 ms |
36700 KB |
Output is correct |