#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pi;
int n; ll k;
vector<pi> adj[300002];
bool chk[300002];
int ans = 0;
ll dfs(int x, int p, ll d)
{
vector<ll> v;
int cnt = 0;
for(auto u : adj[x])
{
int i = u.first;
if(i == p) continue;
ll c = u.second;
ll P = dfs(i, x, c);
v.push_back(P);
}
sort(v.begin(), v.end());
if(v.empty())
{
if(d > k)
{
chk[x] = 1; ans++;
return 2*k+2;
}
return -(d+k+1);
}
else
{
ll D = v[0];
int t = 1;
if(D < 0) { t = -1; D = -D; }
if(D > k && D + d > 2*k+1)
{
chk[x] = 1; ans++;
return t*min(d, k+1);
}
else if(D > k) return t*(D+d);
if(D + d > k) return t*(k+1);
else return t*(D+d);
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> k;
for(int i=1;i<n;i++)
{
int a, b; ll D; cin >> a >> b >> D;
adj[a].push_back({b, D});
adj[b].push_back({a, D});
}
ll P = dfs(1, 0, 0);
if(P < 0) P = -P;
if(P == 0) { chk[1] = 1; ans++; }
if(P > k) { chk[1] = 1; ans++; }
cout << ans << "\n";
for(int i=1;i<=n;i++) if(chk[i]) cout << i << " ";
}
Compilation message
Firefighting.cpp: In function 'll dfs(int, int, ll)':
Firefighting.cpp:15:9: warning: unused variable 'cnt' [-Wunused-variable]
15 | int cnt = 0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
280 ms |
25872 KB |
Output is correct |
2 |
Correct |
283 ms |
25548 KB |
Output is correct |
3 |
Correct |
75 ms |
14060 KB |
Output is correct |
4 |
Correct |
271 ms |
25056 KB |
Output is correct |
5 |
Incorrect |
4 ms |
7244 KB |
Integer parameter [name=F] equals to 3, violates the range [1, 2] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7348 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
4 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7244 KB |
Output is correct |
6 |
Correct |
4 ms |
7340 KB |
Output is correct |
7 |
Correct |
5 ms |
7244 KB |
Output is correct |
8 |
Correct |
6 ms |
7244 KB |
Output is correct |
9 |
Incorrect |
5 ms |
7324 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
4 ms |
7264 KB |
Output is correct |
3 |
Correct |
4 ms |
7300 KB |
Output is correct |
4 |
Correct |
4 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 |
7244 KB |
Output is correct |
8 |
Correct |
4 ms |
7244 KB |
Output is correct |
9 |
Correct |
4 ms |
7244 KB |
Output is correct |
10 |
Incorrect |
5 ms |
7272 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
293 ms |
25596 KB |
Output is correct |
2 |
Incorrect |
123 ms |
17108 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
7500 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
294 ms |
23208 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |