| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 330974 | quindecim | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
const int MX = 200005;
const int INF = 0x3f3f3f3f;
int k, ans = INF, sz[MX], val[1000010], used[300005];
vector<pair<int, int>> adj[MX], tmp;
bitset<MX> vv;
int dfs(int u, int p) {
sz[u] = 1;
for(auto v : adj[u])
if(v.F^p&&!vv[v.F])
sz[u] += dfs(v.F, u);
return sz[u];
}
void dfs2(int u, int p, int l, int d) {
if(k-l<0) return;
if(val[k-l]^INF) ans = min(ans, val[k-l]+d);
tmp.push_back({l, d});
for(auto v : adj[u])
if(v.F^p&&!vv[v.F])
dfs2(v.F, u, l+v.S, d+1);
}
int get_centroid(int u, int p, int ss) {
for(auto v : adj[u])
if(v.F^p&&!vv[v.F]&&sz[v.F]*2>ss)
return get_centroid(v.F, u, ss);
return u;
}
void centroid(int u, int p) {
int C = get_centroid(u, -1, dfs(u, -1));
vv[C] = 1;
int c = 0;
for(auto v : adj[C]) {
if(!vv[v.F]) {
tmp.clear();
dfs2(v.F, C, v.S, 1);
for(auto y : tmp) {
if(y.F<=k) {
val[y.F] = min(val[y.F], y.S);
used[++c] = y.F;
}
}
}
}
ans = min(ans, val[k]);
while(c--) val[used[c]] = INF;
for(auto v : adj[C])
if(v.F^p&&!vv[v.F])
centroid(v.F, C);
}
int best_path(int N, int K, int H[][2], int L[]) {
fill(begin(val), end(val), INF);
k = K;
for(int i = 0; i < N-1; ++i) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
centroid(0, -1);
if(ans==INF) ans = -1;
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n >> k;
int h[n-1][2], l[n-1];
for(int i = 0; i < n-1; ++i)
cin >> h[i][0] >> h[i][1] >> l[i];
cout << best_path(n, k, h, l) << endl;
return 0;
}