#include <iostream>
#include <vector>
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define vi vector<int>
#define vpi vector<pii>
#define fst first
#define snd second
#define pub push_back
using namespace std;
int n;
vector<vpi> adj;
vector<int> ans;
ll k;
ll dfs(int u, int p, ll c)
{
ll deepNonCover = 0, largeCover = -1;
for (auto v : adj[u])
{
if (v.fst ^ p)
{
ll tp = dfs(v.fst, u, v.snd);
if (tp < -1) {deepNonCover = max(deepNonCover, - tp - 1);}
else {largeCover = max(tp, largeCover);}
}
}
//cout << u << " " << deepNonCover << " " << largeCover << "\n";
if (deepNonCover <= largeCover) {return max(-1LL, largeCover - c);}
else
{
if (deepNonCover + c > k || p == -1)
{
ans.push_back(u + 1);
//cout << "INS " << u << " " << k - c << "\n";
return max(-1LL, k - c);
}
else {return - deepNonCover - c - 1;}
}
}
int main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 0; i < n; i++) {adj.pub(vpi());}
for (int i = 0; i < n - 1; i++)
{
int u, v, w; cin >> u >> v >> w;
adj[u - 1].pub({v - 1, w});
adj[v - 1].pub({u - 1, w});
}
dfs(0, -1, 0);
cout << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++)
{
cout<<ans[i];
if (i < ans.size() - 1) {cout << " ";}
}
cout<<"\n";
return 0;
}
Compilation message
Firefighting.cpp: In function 'int main()':
Firefighting.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ans.size(); i++)
~~^~~~~~~~~~~~
Firefighting.cpp:58:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i < ans.size() - 1) {cout << " ";}
~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
397 ms |
30480 KB |
Output is correct |
2 |
Correct |
483 ms |
30516 KB |
Output is correct |
3 |
Correct |
128 ms |
11184 KB |
Output is correct |
4 |
Correct |
474 ms |
29744 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
388 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
512 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
352 ms |
30536 KB |
Output is correct |
2 |
Correct |
184 ms |
14296 KB |
Output is correct |
3 |
Correct |
257 ms |
14752 KB |
Output is correct |
4 |
Correct |
214 ms |
12816 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
447 ms |
25504 KB |
Output is correct |
8 |
Correct |
383 ms |
25416 KB |
Output is correct |
9 |
Correct |
415 ms |
25544 KB |
Output is correct |
10 |
Correct |
415 ms |
25572 KB |
Output is correct |
11 |
Correct |
580 ms |
30516 KB |
Output is correct |
12 |
Correct |
242 ms |
18356 KB |
Output is correct |
13 |
Correct |
175 ms |
11484 KB |
Output is correct |
14 |
Correct |
261 ms |
16888 KB |
Output is correct |
15 |
Correct |
370 ms |
20304 KB |
Output is correct |
16 |
Correct |
406 ms |
21636 KB |
Output is correct |
17 |
Correct |
320 ms |
18408 KB |
Output is correct |
18 |
Correct |
371 ms |
18136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
544 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
668 KB |
Output is correct |
6 |
Correct |
3 ms |
672 KB |
Output is correct |
7 |
Correct |
4 ms |
768 KB |
Output is correct |
8 |
Correct |
4 ms |
680 KB |
Output is correct |
9 |
Correct |
2 ms |
640 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
668 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
4 ms |
680 KB |
Output is correct |
14 |
Correct |
4 ms |
640 KB |
Output is correct |
15 |
Correct |
3 ms |
640 KB |
Output is correct |
16 |
Correct |
3 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
3 ms |
640 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
2 ms |
512 KB |
Output is correct |
21 |
Correct |
3 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
443 ms |
24520 KB |
Output is correct |
2 |
Correct |
412 ms |
23240 KB |
Output is correct |
3 |
Correct |
344 ms |
25032 KB |
Output is correct |
4 |
Correct |
202 ms |
11780 KB |
Output is correct |
5 |
Correct |
439 ms |
37576 KB |
Output is correct |
6 |
Correct |
461 ms |
36000 KB |
Output is correct |
7 |
Correct |
364 ms |
39964 KB |
Output is correct |
8 |
Correct |
454 ms |
38984 KB |
Output is correct |
9 |
Correct |
413 ms |
32712 KB |
Output is correct |
10 |
Correct |
459 ms |
31912 KB |
Output is correct |
11 |
Correct |
422 ms |
42664 KB |
Output is correct |
12 |
Correct |
195 ms |
16988 KB |
Output is correct |
13 |
Correct |
346 ms |
35016 KB |
Output is correct |
14 |
Correct |
447 ms |
30920 KB |
Output is correct |
15 |
Correct |
430 ms |
25292 KB |
Output is correct |
16 |
Correct |
432 ms |
23812 KB |
Output is correct |
17 |
Correct |
391 ms |
23612 KB |
Output is correct |
18 |
Correct |
412 ms |
25288 KB |
Output is correct |
19 |
Correct |
255 ms |
17628 KB |
Output is correct |
20 |
Correct |
111 ms |
10208 KB |
Output is correct |
21 |
Correct |
336 ms |
25304 KB |
Output is correct |