| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1262427 | adscodingzzz | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORD(i, a, b) for (int i = a; i >= b; --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
int n, K, sz[maxn], dp[1000001];
bool isCen[maxn];
vector<pii> g[maxn];
int dfs_sz(int u, int p) {
sz[u] = 1;
for (pii tmp : g[u]) {
int v = tmp.first;
if (v == p || isCen[v]) continue;
sz[u] += dfs_sz(v, u);
}
return sz[u];
}
int findCen(int u, int p, int treeSz) {
for (pii tmp : g[u]) {
int v = tmp.first;
if (v == p || isCen[v] || sz[v] <= treeSz) continue;
return findCen(v, u, treeSz);
}
return u;
}
int mxW, resh = 1e8;
void DP(int u, int p, int w, int h, bool ok) {
if (w > K) return;
if (!ok) {
mxW = max(mxW, w);
resh = min(resh, dp[K - w] + h);
}
else dp[w] = min(dp[w], h);
for (pii tmp : g[u]) {
int v = tmp.first;
if (v == p || isCen[v]) continue;
DP(v, u, w + tmp.second, h + 1, ok);
}
}
void buildCen(int u) {
dfs_sz(u, -1);
int centroid = findCen(u, -1, sz[u] >> 1);
isCen[centroid] = true;
// For centroid
mxW = 0;
dp[0] = 0;
for (pii tmp : g[centroid]) {
int v = tmp.first;
if (isCen[v]) continue;
DP(v, centroid, tmp.second, 1, 0);
DP(v, centroid, tmp.second, 1, 1);
}
FOR(i, 0, mxW) dp[i] = 1e8;
for (pii tmp : g[centroid]) {
int v = tmp.first;
if (isCen[v]) continue;
buildCen(v);
}
}
void solve() {
cin >> n >> K;
FOR(i, 2, n) {
int u, v, w; cin >> u >> v >> w;
++u; ++v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
FOR(i, 0, 1e6) dp[i] = 1e8;
buildCen(1);
cout << (resh == 1e8 ? -1 : resh);
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define TASK "TEST"
if (fopen(TASK".INP", "r")) {
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
solve();
return 0;
}