| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 497686 | XII | 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 fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "IOI11_race"
void Fi(){
if(fopen(PROB".inp", "r")){
freopen(PROB".inp", "r", stdin);
freopen(PROB".out", "w", stdout);
}
}
const int INF = 1e9;
const int N = 2e5 + 1;
const int K = 1e6;
int n, k;
int H[N][2], L[N];
using pi = pair<int, int>;
vector<pi> adj[N];
multiset<pi> s[N];
void enter(){
cin >> n >> k;
FOR(i, 1, n) cin >> H[i][0] >> H[i][1];
FOR(i, 1, n){
cin >> L[i];
adj[H[i][0]].eb(L[i], H[i][1]);
adj[H[i][1]].eb(L[i], H[i][0]);
}
}
int ans = INF;
void dfs(int u, int p = -1){
s[u].insert({0, 0});
for(auto [w, v]: adj[u]) if(v != p){
dfs(v, u);
for(auto p: s[v]) if(p.fi + w <= k){
s[u].insert({p.fi + w, p.se + 1});
} else break;
}
for(auto [w, v]: adj[u]) if(v != p){
for(auto p: s[v]) if(p.fi + w <= k){
s[u].erase(s[u].find({p.fi + w, p.se + 1}));
} else break;
for(auto p: s[v]) if(p.fi + w <= k){
auto it = s[u].lower_bound({k - (p.fi + w), -1});
if(it == s[u].end()) continue;
if((*it).fi == k - (p.fi + w)){
ans = min(ans, p.se + 1 + (*it).se);
}
} else break;
for(auto p: s[v]) if(p.fi + w <= k){
s[u].insert({p.fi + w, p.se + 1});
} else break;
}
}
int main(){
IOS;
Fi();
enter();
dfs(0);
if(ans == INF) cout << -1;
else cout << ans;
return 0;
}