#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int n;
long long k;
vector<pair<int, int>> adj[300006];
vector<int> res;
pair<long long, bool> dfs(int x, int prev = -1) {
long long rev = 0;
bool fine = false;
vector<long long> v;
for (auto &i: adj[x]) if (i.first != prev) {
pair<long long, bool> p = dfs(i.first, x);
long long t = p.first + i.second;
if (!p.second && t > k) {
res.push_back(i.first);
t = i.second - k;
p.second = true;
}
if (t < 0) rev = max(rev, -t), fine = true;
else if (!p.second) v.push_back(t);
else if (!t) fine = true;
}
sort(v.rbegin(), v.rend());
if (v.empty()) return { -rev, fine };
if (v[0] <= rev) return { -rev, true };
if (v[0] >= k) {
res.push_back(x);
return { -k, true };
}
return { v[0], false };
}
int main() {
scanf("%d%lld", &n, &k);
for (int i = 0; i < n - 1; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a--, b--;
adj[a].push_back({ b, c });
adj[b].push_back({ a, c });
}
if (n == 1) {
puts("1\n1");
return 0;
}
if (n == 2) {
if (adj[0][0].second <= k) puts("1\n1");
else puts("2\n1 2");
return 0;
}
if (!dfs(0).second) res.push_back(0);
printf("%d\n", (int)res.size());
for (auto &i: res) printf("%d ", i + 1);
}
Compilation message
Firefighting.cpp: In function 'int main()':
Firefighting.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | scanf("%d%lld", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~
Firefighting.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%d%d%d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
262 ms |
21680 KB |
Output is correct |
2 |
Correct |
265 ms |
21724 KB |
Output is correct |
3 |
Correct |
74 ms |
12680 KB |
Output is correct |
4 |
Correct |
255 ms |
21268 KB |
Output is correct |
5 |
Correct |
4 ms |
7244 KB |
Output is correct |
6 |
Correct |
3 ms |
7244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7244 KB |
Output is correct |
2 |
Correct |
3 ms |
7244 KB |
Output is correct |
3 |
Correct |
3 ms |
7244 KB |
Output is correct |
4 |
Correct |
3 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7244 KB |
Output is correct |
6 |
Correct |
4 ms |
7320 KB |
Output is correct |
7 |
Correct |
4 ms |
7372 KB |
Output is correct |
8 |
Correct |
4 ms |
7372 KB |
Output is correct |
9 |
Correct |
5 ms |
7324 KB |
Output is correct |
10 |
Correct |
4 ms |
7244 KB |
Output is correct |
11 |
Correct |
4 ms |
7244 KB |
Output is correct |
12 |
Correct |
4 ms |
7244 KB |
Output is correct |
13 |
Correct |
4 ms |
7244 KB |
Output is correct |
14 |
Correct |
3 ms |
7324 KB |
Output is correct |
15 |
Correct |
3 ms |
7244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7244 KB |
Output is correct |
2 |
Correct |
3 ms |
7244 KB |
Output is correct |
3 |
Correct |
5 ms |
7244 KB |
Output is correct |
4 |
Correct |
3 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7244 KB |
Output is correct |
6 |
Correct |
4 ms |
7244 KB |
Output is correct |
7 |
Correct |
4 ms |
7320 KB |
Output is correct |
8 |
Correct |
3 ms |
7244 KB |
Output is correct |
9 |
Correct |
4 ms |
7324 KB |
Output is correct |
10 |
Correct |
4 ms |
7244 KB |
Output is correct |
11 |
Correct |
4 ms |
7244 KB |
Output is correct |
12 |
Correct |
4 ms |
7244 KB |
Output is correct |
13 |
Correct |
4 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7288 KB |
Output is correct |
15 |
Correct |
3 ms |
7244 KB |
Output is correct |
16 |
Correct |
4 ms |
7244 KB |
Output is correct |
17 |
Correct |
4 ms |
7244 KB |
Output is correct |
18 |
Correct |
4 ms |
7244 KB |
Output is correct |
19 |
Correct |
4 ms |
7244 KB |
Output is correct |
20 |
Correct |
3 ms |
7244 KB |
Output is correct |
21 |
Correct |
4 ms |
7244 KB |
Output is correct |
22 |
Correct |
4 ms |
7236 KB |
Output is correct |
23 |
Correct |
3 ms |
7244 KB |
Output is correct |
24 |
Correct |
3 ms |
7316 KB |
Output is correct |
25 |
Correct |
4 ms |
7244 KB |
Output is correct |
26 |
Correct |
4 ms |
7244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
277 ms |
21628 KB |
Output is correct |
2 |
Correct |
115 ms |
14408 KB |
Output is correct |
3 |
Correct |
125 ms |
17396 KB |
Output is correct |
4 |
Correct |
103 ms |
16036 KB |
Output is correct |
5 |
Correct |
4 ms |
7320 KB |
Output is correct |
6 |
Correct |
4 ms |
7244 KB |
Output is correct |
7 |
Correct |
254 ms |
23628 KB |
Output is correct |
8 |
Correct |
243 ms |
23644 KB |
Output is correct |
9 |
Correct |
244 ms |
23656 KB |
Output is correct |
10 |
Correct |
263 ms |
23656 KB |
Output is correct |
11 |
Correct |
277 ms |
24876 KB |
Output is correct |
12 |
Correct |
182 ms |
19552 KB |
Output is correct |
13 |
Correct |
116 ms |
14824 KB |
Output is correct |
14 |
Correct |
176 ms |
18752 KB |
Output is correct |
15 |
Correct |
216 ms |
20900 KB |
Output is correct |
16 |
Correct |
235 ms |
21568 KB |
Output is correct |
17 |
Correct |
183 ms |
19816 KB |
Output is correct |
18 |
Correct |
201 ms |
19460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7372 KB |
Output is correct |
2 |
Correct |
6 ms |
7372 KB |
Output is correct |
3 |
Correct |
9 ms |
7372 KB |
Output is correct |
4 |
Correct |
4 ms |
7372 KB |
Output is correct |
5 |
Correct |
5 ms |
7592 KB |
Output is correct |
6 |
Correct |
9 ms |
7596 KB |
Output is correct |
7 |
Correct |
5 ms |
7628 KB |
Output is correct |
8 |
Correct |
5 ms |
7580 KB |
Output is correct |
9 |
Correct |
5 ms |
7500 KB |
Output is correct |
10 |
Correct |
5 ms |
7500 KB |
Output is correct |
11 |
Correct |
5 ms |
7628 KB |
Output is correct |
12 |
Correct |
5 ms |
7372 KB |
Output is correct |
13 |
Correct |
6 ms |
7532 KB |
Output is correct |
14 |
Correct |
6 ms |
7500 KB |
Output is correct |
15 |
Correct |
5 ms |
7416 KB |
Output is correct |
16 |
Correct |
5 ms |
7372 KB |
Output is correct |
17 |
Correct |
5 ms |
7372 KB |
Output is correct |
18 |
Correct |
6 ms |
7500 KB |
Output is correct |
19 |
Correct |
8 ms |
7336 KB |
Output is correct |
20 |
Correct |
5 ms |
7372 KB |
Output is correct |
21 |
Correct |
8 ms |
7500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
254 ms |
18128 KB |
Output is correct |
2 |
Correct |
270 ms |
18012 KB |
Output is correct |
3 |
Correct |
300 ms |
18712 KB |
Output is correct |
4 |
Correct |
91 ms |
12660 KB |
Output is correct |
5 |
Correct |
308 ms |
35448 KB |
Output is correct |
6 |
Correct |
321 ms |
33112 KB |
Output is correct |
7 |
Correct |
340 ms |
40560 KB |
Output is correct |
8 |
Correct |
334 ms |
38908 KB |
Output is correct |
9 |
Correct |
286 ms |
30852 KB |
Output is correct |
10 |
Correct |
288 ms |
29376 KB |
Output is correct |
11 |
Correct |
327 ms |
42044 KB |
Output is correct |
12 |
Correct |
199 ms |
15252 KB |
Output is correct |
13 |
Correct |
321 ms |
31860 KB |
Output is correct |
14 |
Correct |
307 ms |
26848 KB |
Output is correct |
15 |
Correct |
288 ms |
19012 KB |
Output is correct |
16 |
Correct |
249 ms |
18292 KB |
Output is correct |
17 |
Correct |
242 ms |
18116 KB |
Output is correct |
18 |
Correct |
254 ms |
18832 KB |
Output is correct |
19 |
Correct |
171 ms |
15556 KB |
Output is correct |
20 |
Correct |
93 ms |
11944 KB |
Output is correct |
21 |
Correct |
250 ms |
18924 KB |
Output is correct |