| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1204916 | minhpk | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a, b;
vector<pair<int, int>> z[1000005];
int del[1000005], child[1000005], sz;
int cnt1[1000005], cnt[1000005];
int min1 = 1e16;
vector<int> v;
void predfs(int i, int par) {
child[i] = 1;
for (auto p : z[i]) {
if (p.first == par || del[p.first]) continue;
predfs(p.first, i);
child[i] += child[p.first];
}
}
int centroid(int i, int par) {
for (auto p : z[i]) {
if (p.first == par || del[p.first]) continue;
if (child[p.first] > sz / 2) return centroid(p.first, i);
}
return i;
}
void dfs(int i, int par, int val, int len) {
if (val > b) return;
if (cnt[b - val] || val == b) min1 = min(min1, len + cnt[b - val]);
if (cnt1[val] == 0 || cnt1[val] > len) {
v.push_back(val);
cnt1[val] = len;
}
for (auto p : z[i]) {
if (p.first == par || del[p.first]) continue;
dfs(p.first, i, val + p.second, len + 1);
}
}
void skibidi(int i) {
for (int x : v){
cnt1[x] = 0;
cnt[x]=0;
}
v.clear();
cnt[0] = 0;
for (auto p : z[i]) {
if (del[p.first]) continue;
dfs(p.first, i, p.second, 1);
for (int x : v) cnt[x] = min(cnt[x] ? cnt[x] : LLONG_MAX, cnt1[x]);
}
}
void decompose(int i) {
predfs(i, 0);
sz = child[i];
i = centroid(i, 0);
del[i] = 1;
skibidi(i);
for (auto p : z[i]) {
if (del[p.first]) continue;
decompose(p.first);
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b;
for (int i = 1; i < a; i++) {
int x, y, t;
cin >> x >> y >> t;
z[x].push_back({y, t});
z[y].push_back({x, t});
}
decompose(1);
cout << (min1 == 1e16 ? -1 : min1);
return 0;
}