| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1171436 | MinhKien | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
using namespace std;
#define ii pair <int, int>
#define fi first
#define se second
const int N = 2e5 + 10;
const int M = 1e6 + 10;
int n, k, x, y, w;
vector <ii> v[N];
int sz[N], dis[M];
bool solved[N];
int calc_size(int s, int p = -1) {
sz[s] = 1;
for (ii z: v[s]) {
if (z.fi == p || solved[z.fi]) continue;
sz[s] += calc_size(z.fi, s);
}
return sz[s];
}
int FindCentroid(int s, int Size, int p = -1) {
for (ii z: v[s]) {
if (z.fi == p || solved[z.fi]) continue;
if (sz[z.fi] > Size) return FindCentroid(z.fi, Size, s);
}
return s;
}
int ans = 1e9, mx;
void run(int s, int p, int depth, int len, bool filling) {
if (len > k) return;
mx = max(mx, len);
if (filling) {
if (dis[len] == 0) dis[len] = depth;
else dis[len] = min(dis[len], depth);
} else {
if (dis[k - len] != 0) ans = min(ans, dis[k - len] + depth);
if (len == k) ans = min(ans, depth);
}
for (ii z: v[s]) {
if (z.fi == p || solved[z.fi]) continue;
run(z.fi, s, depth + 1, len + z.se, filling);
}
}
void CentroidDecomp(int s = 1) {
int cen = FindCentroid(s, calc_size(s) >> 1);
solved[cen] = true;
mx = 0;
for (ii z: v[cen]) {
if (solved[z.fi]) continue;
run(z.fi, cen, 1, z.se, false);
run(z.fi, cen, 1, z.se, true);
}
fill_n(dis, mx + 1, 0);
for (ii z: v[cen]) {
if (solved[z.fi]) continue;
CentroidDecomp(z.fi);
}
}
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i < n; ++i) {
cin >> x >> y >> w;
++x, ++y;
v[x].push_back(ii(y, w));
v[y].push_back(ii(x, w));
}
CentroidDecomp();
if (ans == 1e9) ans = -1;
cout << ans << "\n";
return 0;
}
//「名前だけで、どうやって君のことを覚えていられるの？」
//「結局、君の名前さえちゃんと分からないんだ？」