| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1297396 | baotoan655 | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
int best_path(int n, int k, int h[][2], int l[]) {
vector<vector<pair<int, int>>> g(n);
for(int i = 0; i < n - 1; ++i) {
int u = h[i][0], v = h[i][1];
g[u].emplace_back(v, l[i]);
g[v].emplace_back(u, l[i]);
}
int ans = n;
vector<bool> del(n, false);
vector<int> sz(n, 0);
function<void(int, int)> get_sz = [&](int u, int p) -> void {
sz[u] = 1;
for(pair<int, int> e : g[u]) {
int v = e.first;
if(v == p || del[v]) continue;
get_sz(v, u);
sz[u] += sz[v];
}
};
function<int(int, int, int)> get_cen = [&](int u, int p, int tot) -> int {
for(pair<int, int> e : g[u]) {
int v = e.first;
if(v == p || del[v]) continue;
if(sz[v] > tot / 2) return get_cen(v, u, tot);
}
return u;
};
map<long long, int> mp;
function<void(int, int, int, long long, bool)> dfs = [&](int u, int p, int depth, long long dist, bool sus) {
if(!sus) {
if(mp.count(k - dist)) ans = min(ans, depth + mp[k - dist]);
} else {
if(mp.count(dist)) mp[dist] = min(mp[dist], depth);
else mp[dist] = depth;
}
for(pair<int, int> e : g[u]) {
int v = e.first, w = e.second;
if(v == p || del[v]) continue;
dfs(v, u, depth + 1, dist + w, sus);
}
};
function<void(int)> centroid = [&](int u) -> void {
get_sz(u, -1);
int cen = get_cen(u, -1, sz[u]);
del[cen] = true;
mp.clear();
mp[0] = 0;
for(pair<int, int> e : g[cen]) {
int v = e.first, w = e.second;
if(del[v]) continue;
dfs(v, cen, 1, w, false);
dfs(v, cen, 1, w, true);
}
for(pair<int, int> e : g[cen]) {
int v = e.first;
if(del[v]) continue;
centroid(v);
}
};
centroid(1);
if(ans >= n) ans = -1;
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
file("A") else file("task");
int n, k;
cin >> n >> k;
int h[n - 1][2], l[n - 1];
for(int i = 0; i < n; ++i) {
int u, v, c;
cin >> u >> v >> c;
h[i][0] = u;
h[i][1] = v;
l[i] = c;
}
cout << best_path(n, k, h, l) << '\n';
return 0;
}