| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 890170 | anarch_y | Race (IOI11_race) | C++17 | 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;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
const int maxn = 100001;
int N, K;
vector<int> adj[maxn];
vector<pair<int, int>> adj2[maxn];
int sub[maxn];
bool done[maxn];
int subtree_size(int s, int p){
sub[s] = 1;
for(auto u: adj[s]){
if(u == p or done[u]) continue;
sub[s] += subtree_size(u, s);
}
return sub[s];
}
int get_centroid(int s, int p, int num){
for(auto u: adj[s]){
if(u == p or done[u]) continue;
if(2*sub[u] > num) return get_centroid(u, s, num);
}
return s;
}
int min_d[1000001] = {1};
int mxd; int ans = 1e9;
void calc(int s, int p, int ok, int d, int wt){
if(wt > K) return;
mxd = max(mxd, wt);
if(ok) min_d[wt] = min(min_d[wt], d);
else ans = min(ans, d+min_d[K-wt]);
for(auto &[u, t]: adj2[s]){
if(u == p or done[u]) continue;
calc(u, s, ok, d+1, wt+t);
}
}
void centroid_decomp(int s){
int num = subtree_size(s, 0);
int cent = get_centroid(s, 0, num);
int mxd = 0;
for(auto &[u, w]: adj2[cent]){
if(done[u]) continue;
calc(u, cent, false, 1, w);
calc(u, cent, true, 1, w);
}
fill(min_d+1, min_d+mxd+1, 1e9);
done[cent] = true;
for(auto u: adj[cent]){
if(!done[u]) centroid_decomp(u);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
int H[N-1][2];
for(int i=0; i<N-1; i++){
int a, b; cin >> a >> b; a++; b++;
H[i][0] = a; H[i][1] = b;
}
int L[N-1];
for(int i=0; i<N-1; i++) cin >> L[i];
for(int i=0; i<N-1; i++){
int a = H[i][0], b = H[i][1], w = L[i];
adj[a].pb(b); adj[b].pb(a);
adj2[a].pb({b, w}); adj2[b].pb({a, w});
}
fill(min_d+1, min_d+1000001, 1e9);
centroid_decomp(1);
cout << (ans != 1e9 ? ans : -1);
}