| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 753954 | phoenix0423 | 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;
typedef long long ll;
typedef pair<int, int> pll;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int maxn = 2e5 + 5;
ll n, k, ans = 1e9;
vector<pll> adj[maxn];
ll w[maxn], vis[maxn], siz[maxn];
map<ll, ll> all, tmp;
// find centroid, calculate answer for centroid, remove the node and recurse for further centroids
void dfssz(int pos, int prev){
siz[pos] = 1;
for(auto [x, idx] : adj[pos]){
if(x == prev || vis[x]) continue;
dfssz(x, pos);
siz[pos] += siz[x];
}
}
void dfsans(int pos, int prev, ll dis, ll cnt){
if(tmp.find(dis) != tmp.end()) tmp[dis] = min(tmp[dis], cnt);
else tmp[dis] = cnt;
for(auto [x, idx] : adj[pos]){
if(x == prev || vis[x]) continue;
dfsans(x, pos, dis + w[idx], cnt + 1);
}
}
int get_centroid(int pos, int prev, int sz){
for(auto [x, idx] : adj[pos]){
if(x != prev && !vis[x] && siz[x] > sz / 2) return get_centroid(x, pos, sz);
}
return pos;
}
void centroid_decomposition(int pos){
dfssz(pos, -1);
int centroid = get_centroid(pos, -1, siz[pos]);
vis[centroid] = 1;
all.clear();
all[0] = 0;
for(auto [x, idx] : adj[centroid]){
tmp.clear();
if(vis[x]) continue;
dfsans(x, -1, w[idx], 1);
for(auto [dis, cnt] : tmp){
if(all.find(k - dis) != all.end()) {
ans = min(ans, cnt + all[k - dis]);
}
}
for(auto [dis, cnt] : tmp){
if(all.find(dis) != all.end()) all[dis] = min(all[dis], cnt);
else all[dis] = cnt;
}
}
for(auto [x, idx] : adj[centroid]){
if(vis[x]) continue;
centroid_decomposition(x);
}
}
int main(void){
cin>>n>>k;
for(int i = 0; i < n - 1; i++){
int a, b;
cin>>a>>b;
adj[a].eb(b, i);
adj[b].eb(a, i);
}
for(int i = 0; i < n - 1; i++) cin>>w[i];
centroid_decomposition(0);
cout<<(ans > 1e7 ? -1 : ans)<<"\n";
}