#include <bits/stdc++.h>
typedef long long ll;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
ll n, k;
std::cin >> n >> k;
std::vector<std::vector<std::pair<ll, ll>>> adj(n + 1);
ll min_w = 1e15;
for (ll i = 0, u, v, w; i < n - 1; ++i) {
std::cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
min_w = std::min(min_w, w);
}
if (k < min_w) {
std::cout << n << '\n';
for (ll i = 1; i <= n; ++i) {
std::cout << i << ' ';
}
std::cout << '\n';
return 0;
}
std::pair<ll, ll> ans = {1e15, -1};
for (ll mask = 1; mask < (1 << n); ++mask) {
std::priority_queue<std::pair<ll, ll>> pq;
std::vector<bool> vis(n + 1);
std::vector<ll> dist(n + 1, 1e15);
dist[0] = 0;
for (ll i = 0; i < n; ++i) {
if (mask & (1 << i)) {
dist[i + 1] = 0;
pq.push({0, i + 1});
}
}
while (!pq.empty()) {
auto [d, node] = pq.top();
pq.pop();
if (vis[node]) {
continue;
}
vis[node] = true;
d *= -1;
for (auto &[ch, w] : adj[node]) {
if (d + w < dist[ch]) {
dist[ch] = d + w;
pq.push({-dist[ch], ch});
}
}
}
if (*std::max_element(dist.begin(), dist.end()) <= k) {
ans = std::min(ans, {__builtin_popcount(mask), mask});
}
}
std::cout << ans.first << '\n';
for (ll i = 0; i < n; ++i) {
if (ans.second & (1 << i)) {
std::cout << i + 1 << ' ';
}
}
std::cout << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
131 ms |
25172 KB |
Output is correct |
2 |
Correct |
127 ms |
25408 KB |
Output is correct |
3 |
Correct |
39 ms |
9556 KB |
Output is correct |
4 |
Correct |
144 ms |
24740 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
436 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
31 ms |
348 KB |
Output is correct |
6 |
Correct |
39 ms |
436 KB |
Output is correct |
7 |
Correct |
72 ms |
344 KB |
Output is correct |
8 |
Correct |
73 ms |
344 KB |
Output is correct |
9 |
Correct |
71 ms |
348 KB |
Output is correct |
10 |
Correct |
74 ms |
348 KB |
Output is correct |
11 |
Correct |
72 ms |
348 KB |
Output is correct |
12 |
Correct |
82 ms |
344 KB |
Output is correct |
13 |
Correct |
74 ms |
344 KB |
Output is correct |
14 |
Correct |
4 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
428 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
79 ms |
344 KB |
Output is correct |
4 |
Correct |
36 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
75 ms |
436 KB |
Output is correct |
10 |
Correct |
80 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
85 ms |
436 KB |
Output is correct |
13 |
Correct |
37 ms |
348 KB |
Output is correct |
14 |
Correct |
41 ms |
348 KB |
Output is correct |
15 |
Correct |
92 ms |
440 KB |
Output is correct |
16 |
Correct |
49 ms |
348 KB |
Output is correct |
17 |
Correct |
91 ms |
348 KB |
Output is correct |
18 |
Correct |
43 ms |
344 KB |
Output is correct |
19 |
Correct |
82 ms |
348 KB |
Output is correct |
20 |
Correct |
92 ms |
348 KB |
Output is correct |
21 |
Correct |
92 ms |
452 KB |
Output is correct |
22 |
Correct |
86 ms |
348 KB |
Output is correct |
23 |
Correct |
90 ms |
348 KB |
Output is correct |
24 |
Correct |
85 ms |
344 KB |
Output is correct |
25 |
Correct |
0 ms |
344 KB |
Output is correct |
26 |
Correct |
85 ms |
432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
25172 KB |
Output is correct |
2 |
Execution timed out |
3020 ms |
16724 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
604 KB |
Expected int32, but "1000000000000000" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3057 ms |
27948 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |