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;
const int N = 1e6+2;
using ll = long long;
const int mod = 1e9 + 7;
ll lim;
ll dist1[200002], dist2[200002], cnt, k, n;
bool viz[200002], ok[200002];
vector<pair<int, int>>G[200002];
void dfs (int nod, int par, ll last) {
dist1[nod] = 0;
dist2[nod] = -1;
for (auto [u, x] : G[nod]) {
if (u == par)
continue;
dfs(u, nod, x);
if (ok[u])
dist2[nod] = max(dist2[nod], lim - (x + dist2[u]));
else
dist1[nod] = max(dist1[nod], x + dist1[u]);
}
if (dist1[nod] <= dist2[nod]) {
ok[nod] = 1;
return;
}
if (dist1[nod] + last > lim) {
ok[nod] = 1;
viz[nod] = 1;
cnt++;
return;
}
ok[nod] = 0;
return;
}
const ll inf = 1e17;
bool solve () {
cnt = 0;
memset(viz, 0, sizeof(viz));
dfs(1, 0, 2*inf);
return (cnt <= k);
}
void cb () {
ll st = 0, dr = inf, ans;
while (st <= dr) {
lim = (st + dr) / 2;
if (solve()) {
ans = lim;
dr = lim - 1;
}
else
st = lim +1;
}
cout << ans << "\n";
lim = ans;
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i < n; i++) {
int x, y, z;
cin >> x >> y >> z;
G[x].push_back({y, z});
G[y].push_back({x, z});
}
cb();
memset(viz, 0, sizeof(viz));
cnt = 0;
dfs(1, 0, 2*inf);
for (int i = 1; i <= n; i++)
if (viz[i])
cout << i << " ";
for (int i = 1; i <= n && cnt < k; i++)
if (!viz[i])
cout << i << " ", cnt++;
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'void dfs(int, int, ll)':
Main.cpp:17:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
17 | for (auto [u, x] : G[nod]) {
| ^
Main.cpp: In function 'void cb()':
Main.cpp:59:7: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | lim = ans;
| ~~~~^~~~~
# | 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... |