# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
827411 | Kubogi | Parkovi (COCI22_parkovi) | C++17 | 812 ms | 40284 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
const int maxn = 2e5+4, inf = 1e18;
int n, k;
vector<pair<int, int> > adj[maxn];
int f[maxn], g[maxn];
bool chosen[maxn];
void dfs(int u, int p, int val, int wp) {
for (auto e: adj[u]) {
int v = e.first, w = e.second;
if (v != p) {
dfs(v, u, val, w);
f[u] = max(f[u], w + f[v]);
g[u] = min(g[u], w + g[v]);
}
}
if (f[u] + g[u] > val) {
if (u == 1) {
chosen[u] = (g[u] > val);
return;
}
if (f[u] + wp > val) {
chosen[u] = true;
f[u] = -inf, g[u] = 0;
}
}
}
int cnt(int val) {
fill(f+1, f+1+n, 0);
fill(g+1, g+1+n, inf);
fill(chosen+1, chosen+1+n, false);
dfs(1, 0, val, 0);
int res = 0;
for (int i = 1; i <= n; i++) {
res += chosen[i];
}
return res;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
fileio("ktree");
// freopen("debug.txt", "w", stderr);
cin >> n >> k;
for (int i = 1; i < n; i++) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int l = 0, r = 1e15;
while (l <= r) {
int mid = (l+r)>>1;
if (cnt(mid) <= k) r = mid-1;
else l = mid+1;
}
cout << l << "\n";
int x = cnt(l);
for (int i = 1; i <= n; i++) {
if (chosen[i]) cout << i << " ";
else if (x < k) {
cout << i << " ";
x++;
}
}
return 0 ^ 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |