#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
typedef pair<int,int> P;
vector<vector<P>> adj;
bool type[300005];
vector<int> ans;
int K;
int dfs(int c, int p, int len) {
int ma = 0, mi = INF;
for(P n2 : adj[c]) {
int n = n2.first;
int d = n2.second;
if(n==p) continue;
int l = dfs(n, c, d);
if(type[n]) mi = min(mi, l); // sobang case
else ma = max(ma, l);
}
//cout << c << ' ' <<ma << ' ' << mi << '\n';
if(mi == INF) {
if(len == -1 || ma + len > K) {
type[c] = true;
ans.push_back(c);
return len;
}
type[c] = false;
return len + ma;
}
if(mi + ma > K) {
type[c] = true;
ans.push_back(c);
return len;
}
if(mi + len <= K) {
type[c] = true;
return mi + len;
}
type[c] = false;
return len;
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N >> K;
int i;
adj.resize(N);
for(i=0;i<N-1;i++) {
int a, b, c;
cin >> a >> b >>c;
adj[a-1].push_back(P(b-1, c));
adj[b-1].push_back(P(a-1, c));
}
dfs(0, -1, -1);
cout << ans.size() << '\n';
for(i=0;i<ans.size();i++) cout << ans[i] + 1 << ' ';
}
Compilation message
Firefighting.cpp: In function 'int main()':
Firefighting.cpp:58:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(i=0;i<ans.size();i++) cout << ans[i] + 1 << ' ';
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
302 ms |
28088 KB |
Output is correct |
2 |
Correct |
264 ms |
28012 KB |
Output is correct |
3 |
Correct |
71 ms |
10608 KB |
Output is correct |
4 |
Correct |
255 ms |
27248 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
264 ms |
28216 KB |
Output is correct |
2 |
Incorrect |
114 ms |
14940 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
228 ms |
22976 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |