| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 881991 | chanhchuong123 | Race (IOI11_race) | 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;
#define task ""
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int INF = 1e9 + 7;
const int MAX = 200020;
int n, k;
vector<pair<int, int>> adj[MAX];
int sz[MAX];
bool rem[MAX];
int dfsSZ(int u, int p) {
sz[u] = 1;
for (auto [v, w]: adj[u]) if (v != p && !rem[v]) {
sz[u] += dfsSZ(v, u);
}
return sz[u];
}
int findCentroid(int u, int p, int n) {
for (auto [v, w]: adj[u]) if (v != p && !rem[v]) {
if (2 * sz[v] > n)
return findCentroid(v, u, n);
}
return u;
}
int h[MAX];
int dep[MAX];
int res = +INF;
int maxHigh[1000010];
void dfs(int u, int p, bool upd) {
if (dep[u] > k) return;
if (!upd) res = min(res, h[u] + maxHigh[k - dep[u]]);
if (upd) maxHigh[dep[u]] = min(maxHigh[dep[u]], h[u]);
for (auto [v, w]: adj[u]) if (v != p && !rem[v]) {
dep[v] = dep[u] + w;
h[v] = h[u] + 1;
dfs(v, u, upd);
}
}
void del(int u, int p) {
if (dep[u] > k) return;
maxHigh[dep[u]] = +INF;
for (auto [v, w]: adj[u]) if (v != p && !rem[v]) del(v, u);
}
void solve(int u, int p) {
int c = findCentroid(u, p, dfsSZ(u, p)); rem[c] = true;
dep[c] = h[c] = 0;
for (auto [v, w]: adj[c]) if (v != p && !rem[v]) {
dep[v] = dep[c] + w;
h[v] = h[c] + 1;
dfs(v, c, 0);
dfs(v, c, 1);
}
for (auto [v, w]: adj[c]) if (v != p && !rem[v]) {
del(v, c);
}
for (auto [v, w]: adj[c]) if (v != p && !rem[v]) {
solve(v, c);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n >> k;
for (int i = 0; i <= k; ++i) {
maxHigh[i] = +INF;
}
for (int i = 1; i < n; ++i) {
int u, v, l; cin >> u >> v >> l;
adj[u].emplace_back(v, l);
adj[v].emplace_back(u, l);
}
maxHigh[0] = 0; solve(0, -1);
cout << (res == INF ? -1 : res);
return 0;
}