#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<pair<int, ll>> adj[300300];
pair<int, ll> par[300300];
ll dep[300300];
int deg[300300], visited[300300];
priority_queue<pair<ll, int>> pq;
void dfs(int s, int pa = -1){
deg[s] = adj[s].size();
for (auto &v:adj[s]) if (v.first!=pa){
par[v.first] = {s, v.second};
dep[v.first] = dep[s] + v.second;
dfs(v.first, s);
}
}
int cnt;
void dfs2(int s, ll K){
visited[s] = cnt;
for (auto &v:adj[s]) if (visited[v.first]!=cnt){
if (v.second<=K) dfs2(v.first, K-v.second);
else{
deg[v.first]--;
if (deg[v.first]==1 && !visited[v.first]) pq.emplace(dep[v.first], v.first);
}
}
}
int main(){
int n;
ll D;
scanf("%d %lld", &n, &D);
for (int i=0;i<n-1;i++){
int x, y;
ll z;
scanf("%d %d %lld", &x, &y, &z);
adj[x].emplace_back(y, z);
adj[y].emplace_back(x, z);
}
if (n==1) {printf("1\n1\n"); return 0;}
dfs(1);
for (int i=1;i<=n;i++) if (deg[i]==1) pq.emplace(dep[i], i);
vector<int> ans;
while(!pq.empty()){
auto cur = pq.top(); pq.pop();
if (visited[cur.second]) continue;
int s = cur.second;
ll rem = D;
while(par[s].first && par[s].second<=rem){
rem -= par[s].second;
s = par[s].first;
}
ans.push_back(s);
cnt++;
dfs2(s, D);
}
printf("%d\n", (int)ans.size());
for (auto &x:ans) printf("%d ", x);
return 0;
}
Compilation message
Firefighting.cpp: In function 'int main()':
Firefighting.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | scanf("%d %lld", &n, &D);
| ~~~~~^~~~~~~~~~~~~~~~~~~
Firefighting.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | scanf("%d %d %lld", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
482 ms |
37896 KB |
Output is correct |
2 |
Correct |
490 ms |
37924 KB |
Output is correct |
3 |
Correct |
150 ms |
19012 KB |
Output is correct |
4 |
Correct |
441 ms |
36840 KB |
Output is correct |
5 |
Correct |
4 ms |
7372 KB |
Output is correct |
6 |
Correct |
4 ms |
7244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7372 KB |
Output is correct |
2 |
Correct |
3 ms |
7256 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
4 ms |
7372 KB |
Output is correct |
5 |
Correct |
6 ms |
7372 KB |
Output is correct |
6 |
Correct |
4 ms |
7372 KB |
Output is correct |
7 |
Correct |
4 ms |
7372 KB |
Output is correct |
8 |
Correct |
4 ms |
7484 KB |
Output is correct |
9 |
Correct |
4 ms |
7372 KB |
Output is correct |
10 |
Correct |
4 ms |
7372 KB |
Output is correct |
11 |
Correct |
4 ms |
7372 KB |
Output is correct |
12 |
Correct |
4 ms |
7372 KB |
Output is correct |
13 |
Correct |
4 ms |
7372 KB |
Output is correct |
14 |
Correct |
4 ms |
7352 KB |
Output is correct |
15 |
Correct |
4 ms |
7348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7372 KB |
Output is correct |
2 |
Correct |
4 ms |
7376 KB |
Output is correct |
3 |
Correct |
4 ms |
7372 KB |
Output is correct |
4 |
Correct |
4 ms |
7372 KB |
Output is correct |
5 |
Correct |
4 ms |
7372 KB |
Output is correct |
6 |
Correct |
5 ms |
7372 KB |
Output is correct |
7 |
Correct |
4 ms |
7244 KB |
Output is correct |
8 |
Correct |
4 ms |
7244 KB |
Output is correct |
9 |
Correct |
4 ms |
7372 KB |
Output is correct |
10 |
Correct |
4 ms |
7372 KB |
Output is correct |
11 |
Correct |
4 ms |
7256 KB |
Output is correct |
12 |
Correct |
4 ms |
7372 KB |
Output is correct |
13 |
Correct |
4 ms |
7372 KB |
Output is correct |
14 |
Correct |
4 ms |
7372 KB |
Output is correct |
15 |
Correct |
4 ms |
7372 KB |
Output is correct |
16 |
Correct |
4 ms |
7372 KB |
Output is correct |
17 |
Correct |
4 ms |
7372 KB |
Output is correct |
18 |
Correct |
5 ms |
7352 KB |
Output is correct |
19 |
Correct |
4 ms |
7372 KB |
Output is correct |
20 |
Correct |
4 ms |
7372 KB |
Output is correct |
21 |
Correct |
4 ms |
7352 KB |
Output is correct |
22 |
Correct |
4 ms |
7372 KB |
Output is correct |
23 |
Correct |
4 ms |
7372 KB |
Output is correct |
24 |
Correct |
4 ms |
7372 KB |
Output is correct |
25 |
Correct |
4 ms |
7356 KB |
Output is correct |
26 |
Correct |
4 ms |
7356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
444 ms |
37736 KB |
Output is correct |
2 |
Correct |
185 ms |
23864 KB |
Output is correct |
3 |
Correct |
203 ms |
24248 KB |
Output is correct |
4 |
Correct |
163 ms |
22040 KB |
Output is correct |
5 |
Correct |
4 ms |
7372 KB |
Output is correct |
6 |
Correct |
4 ms |
7224 KB |
Output is correct |
7 |
Execution timed out |
3073 ms |
38468 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7500 KB |
Output is correct |
2 |
Correct |
6 ms |
7616 KB |
Output is correct |
3 |
Correct |
5 ms |
7472 KB |
Output is correct |
4 |
Correct |
5 ms |
7488 KB |
Output is correct |
5 |
Correct |
60 ms |
7824 KB |
Output is correct |
6 |
Correct |
59 ms |
7752 KB |
Output is correct |
7 |
Correct |
41 ms |
7756 KB |
Output is correct |
8 |
Correct |
42 ms |
7824 KB |
Output is correct |
9 |
Correct |
35 ms |
7756 KB |
Output is correct |
10 |
Correct |
35 ms |
7756 KB |
Output is correct |
11 |
Correct |
62 ms |
7756 KB |
Output is correct |
12 |
Correct |
5 ms |
7500 KB |
Output is correct |
13 |
Correct |
45 ms |
7836 KB |
Output is correct |
14 |
Correct |
35 ms |
7696 KB |
Output is correct |
15 |
Correct |
6 ms |
7700 KB |
Output is correct |
16 |
Correct |
5 ms |
7500 KB |
Output is correct |
17 |
Correct |
6 ms |
7540 KB |
Output is correct |
18 |
Correct |
5 ms |
7628 KB |
Output is correct |
19 |
Correct |
5 ms |
7628 KB |
Output is correct |
20 |
Correct |
5 ms |
7488 KB |
Output is correct |
21 |
Correct |
6 ms |
7744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
369 ms |
33736 KB |
Output is correct |
2 |
Correct |
309 ms |
38592 KB |
Output is correct |
3 |
Correct |
344 ms |
41172 KB |
Output is correct |
4 |
Correct |
148 ms |
22976 KB |
Output is correct |
5 |
Execution timed out |
3024 ms |
49048 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |