| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 896542 | BF_01 | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005
#define K 1000005
#define fi first
#define se second
#define oo 1e18
typedef pair<int, int> ii;
int t, n, k, dd[K], res = oo, siz[N];
set<ii> adj[N];
vector<int> rs;
void getsiz(int u, int p){
siz[u] = 1;
for (auto x : adj[u]){
if (x.fi == p) continue;
getsiz(x.fi, u);
siz[u] += siz[x.fi];
}
}
int centroid (int u, int p, int n){
for (auto x : adj[u]){
if (x.fi == p) continue;
if (siz[x.fi] > n / 2) return centroid(x.fi, u, n);
}
return u;
}
void dfs(int u, int ww, int check, int dep, int p){
if (ww > k) return;
if (!check){
if (ww == k) res = min(res, dep);
else if (dd[k - ww] != 0) res = min(res, dep + dd[k - ww]);
}
else {
if (dd[ww] == 0) rs.push_back(ww);
if (dd[ww] == 0 || dd[ww] > dep) dd[ww] = dep;
}
for (auto x : adj[u]){
int v = x.fi;
int w = x.se;
if (ww + w > k) continue;
if (v == p) continue;
dfs(v, ww + w, check, dep + 1, u);
}
}
void initcentroid(int u, int p){
getsiz(u, p);
int c = centroid(u, p, siz[u]);
// dfs(c, p, 1);
// dfs(c, p, 0);
for (auto x : adj[c]){
dfs(x.fi, x.se, 0, 1, c);
dfs(x.fi, x.se, 1, 1, c);
}
for (auto x : rs) dd[x] = 0;
rs.clear();
vector<ii> tmp(adj[c].begin(), adj[c].end());
for (auto x : tmp){
int v = x.fi, w = x.se;
adj[v].erase({c, w});
adj[c].erase({v, w});
initcentroid(v, c);
}
}
void solve(){
cin >> n >> k;
for (int i = 1; i <= n - 1; i++){
int u, v, w;
u++; ++v;
cin >> u >> v >> w;
adj[u].insert({v, w});
adj[v].insert({u, w});
}
initcentroid(1, -1);
if (res == oo) cout << -1;
else
cout << res;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int t = 1;
while (t--){
solve();
}
return 0;
}