| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 384487 | dongliu0426 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 200001;
const int K = 1000010;
const int inf = 0x3f3f3f3f;
struct L {
int x, w;
L *next;
} *aa[N];
void link(int i, int j, int k) {
L *l = new L();
l->x = j, l->w = k;
l->next = aa[i];
aa[i] = l;
};
int n, k, ss[N], dep, cc[K];
bool vv[N];
int ans = inf;
int subtree(int x, int p = 0) {
ss[x] = 1;
for (L *y = aa[x]; y; y = y->next)
if (!vv[y->x] && y->x != p)
ss[x] += subtree(y->x, x);
return ss[x];
}
int centroid(int dd, int x, int p = 0) {
for (L *y = aa[x]; y; y = y->next)
if (!vv[y->x] && y->x != p && ss[y->x] >= dd)
return centroid(dd, y->x, x);
return x;
}
void _count(int x, int p, int d, int dd) {
if (d > k) return;
dep = max(dep, d);
ans = min(ans, cc[k - d] + dd);
for (L *y = aa[x]; y; y = y->next)
if (!vv[y->x] && y->x != p)
_count(y->x, x, d + y->w, dd + 1);
}
void _fill(int x, int p, int d, int dd) {
if (d > k) return;
cc[d] = min(cc[d], dd);
for (L *y = aa[x]; y; y = y->next)
if (!vv[y->x] && y->x != p)
_fill(y->x, x, d + y->w, dd + 1);
}
void decomp(int x = 1) {
int c = centroid(subtree(x) / 2, x);
vv[c] = 1;
dep = 0;
for (L *y = aa[c]; y; y = y->next)
if (!vv[y->x]) {
_count(y->x, c, y->w, 1);
_fill(y->x, c, y->w, 1);
}
for (int i = 1; i <= dep; ++i)
cc[i] = inf;
for (L *y = aa[c]; y; y = y->next)
if (!vv[y->x])
decomp(y->x);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
scanf("%d%d", &n, &k);
for (int i = 1, x, y, z; i < n; ++i) {
scanf("%d%d%d", &x, &y, &z); ++x, ++y;
link(x, y, z), link(y, x, z);
}
memset(cc, 0x3f, sizeof(cc)); cc[0] = 0;
decomp();
printf("%d\n", (ans == inf ? -1 : ans));
}