// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
using db = long double;
const int MOD = 1e9 + 7;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N; ll K; cin >> N >> K;
V<vpi> adj(N); for(int i = 0; i < N-1; i++) {
int u, v, w; cin >> u >> v >> w; --u, --v;
adj[u].pb(mp(v, w));
adj[v].pb(mp(u, w));
}
vi ans; vi G(N);
function<ll(int, int, int)> dfs = [&](int u, int p, int d) {
vpl chd; for(auto& e : adj[u]) {
auto [v, w] = e; if (v == p) continue;
ll f = dfs(v, u, w) + w;
if (f > 0 && G[v]) f = 0, G[v] = 0;
chd.pb(mp(f, v));
}
sort(begin(chd), end(chd), [&](auto a, auto b) {
if (a.f == b.f) return G[a.s] < G[b.s];
return a.f < b.f;
});
// cout << u << endl;
// for(auto x : chd) {
// cout << x.f << " " << x.s << " " << G[x.s] << endl;
// }
// cout << endl;
ll far = 0;
if (sz(chd) == 0) {
far = 0;
} else {
bool good = (chd.front().f + chd.back().f) <= 0;
if (good) { // good subtree (take front)
G[u] = G[chd.front().s];
far = chd.front().f;
} else { // bad subtree (take back)
far = chd.back().f;
}
}
if (!G[u] && (far + d) > K) {
G[u] = 1; ans.pb(u);
return -K;
} else return far;
};
dfs(0, -1, MOD);
cout << sz(ans) << nl;
for(auto& x : ans) cout << x + 1 << " ";
cout << nl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
251 ms |
22852 KB |
Output is correct |
2 |
Correct |
223 ms |
22888 KB |
Output is correct |
3 |
Correct |
49 ms |
8740 KB |
Output is correct |
4 |
Correct |
249 ms |
22232 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
236 ms |
22964 KB |
Output is correct |
2 |
Incorrect |
106 ms |
12204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Incorrect |
1 ms |
468 KB |
Integer parameter [name=F] equals to 0, violates the range [1, 2576] |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
229 ms |
19000 KB |
Output is correct |
2 |
Incorrect |
161 ms |
18132 KB |
Integer parameter [name=F] equals to 0, violates the range [1, 276153] |
3 |
Halted |
0 ms |
0 KB |
- |