| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 536135 | Alex_tz307 | Parkovi (COCI22_parkovi) | C++17 | 0 ms | 0 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;
const int kN = 2e5;
const int64_t INF = 1e18L;
vector<pair<int, int>> g[1 + kN];
int N, depth[1 + kN], sol[kN];
bitset<1 + kN> mark, covered;
void maxSelf(int64_t &x, int64_t y) {
if (x < y) {
x = y;
}
}
void minSelf(int64_t &x, int64_t y) {
if (y < x) {
x = y;
}
}
int64_t dfs(int u, int par, int64_t radius) {
if ((int)g[u].size() == 1 && par) {
return 0;
}
int64_t mx = -INF, mn = INF;
for (auto it : g[u]) {
int v, w;
tie(v, w) = it;
if (v != par) {
int64_t ret = dfs(v, u, radius);
if (ret == 0 && covered[v]) { // v este acoperit si nimic din subarborele sau nu ma mai poate ajuta mai mult decat u
maxSelf(mx, 0LL);
minSelf(mn, 0LL);
continue;
}
if (ret < 0 && ret + w <= 0) { // u este acoperit
covered[u] = true;
}
if (ret < 0 && ret + w > 0) { // v sigur e acoperit si incepand de la u nu se mai acopera nimic nou, deci "resetez"
ret = 0;
} else { // creste distanta fata de ultimul nod marcat si mai mult
ret += w;
}
if (ret > radius) { // trebuie sa il marchez pe v acum ca sa acopere alte noduri nemarcate, pentru ca deja u nu poate ajuta
sol[N++] = v;
mark[v] = true;
covered[v] = true;
ret = min(-radius + w, 0LL); // aproape analog cu cazurile anterioare
if (w <= radius) {
covered[u] = true;
}
}
maxSelf(mx, ret);
minSelf(mn, ret);
}
}
if (mx <= -mn) { // nodul de unde trebuie sa incep sa marchez din cauza lui mx(ca s-ar termina) va fi ori acoperit ori voi mai putea amana o eventuala marcare a sa datorita lui mn
return mn;
}
return mx;
}
bool check(int64_t m, int k) {
N = 0;
mark.reset();
covered.reset();
if (dfs(1, 0, m) > 0) {
sol[N++] = 1;
mark[1] = true;
} else if (!covered[1]) {
sol[N++] = 1;
mark[1] = true;
}
return N <= k;
}
void testCase() {
int n, k;
cin >> n >> k;
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
int64_t ans = 0, step = (1LL << 50);
while (step) {
if (!check(ans | step, k)) {
ans |= step;
}
step /= 2;
}
ans += 1;
check(ans, k);
for (int v = 1; v <= n && N < k; ++v) {
if (!mark[v]) {
sol[N++] = v;
}
}
cout << ans << '\n';
for (int i = 0; i < k; ++i) {
cout << sol[i] << ' ';
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests = 1;
for (int tc = 1; tc <= tests; ++tc) {
testCase();
}
return 0;
}