| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 445720 | naman1601 | 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 big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define debug(text) if(do_debug) {cout << (#text) << ": " << text << endl;}
#define nl "\n"
// making some things easily accessible
// push_back pop_back emplace_back make_pair lower_bound upper_bound reserve resize reverse
const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;
const int maxn = 2e5 + 5;
int n_nodes, n_edges, rl;
vector<array<int, 2>> adj[maxn];
// int depth[maxn];
// vector<int> rev[maxn];
// vector<int> path;
big ans = infinity;
struct ds {
map<big, big> m;
big extra_w = 0;
big extra_l = 0;
};
ds state[maxn];
void merge(ds& a, ds& b) {
if(a.m.size() < b.m.size()) swap(a, b);
for(auto p : b.m) {
big cur_w = p.fe + b.extra_w;
big cur_l = p.se + b.extra_l;
if(cur_w > rl) break;
big rq = rl - cur_w;
big look_for = rq - a.extra_w;
if(a.m.find(look_for) != a.m.end()) {
ans = min(ans, cur_l + a.m[look_for] + a.extra_l);
}
// if(cur_w == rl) {
// ans = min(ans, cur_l + a.extra_l);
// } else {
// big rq = rl - cur_w;
// big look_for = rq - a.extra_w;
// if(a.m.find(look_for) != a.m.end()) {
// ans = min(ans, a.m[look_for] + a.extra_l);
// }
// }
}
for(auto p : b.m) {
big cur_w = p.fe + b.extra_w - a.extra_w;
big cur_l = p.se + b.extra_l - a.extra_l;
if(a.m.find(cur_w) != a.m.end()) {
a.m[cur_w] = min(a.m[cur_w], cur_l);
} else {
a.m[cur_w] = cur_l;
}
}
}
void dfs(int node, int parent) {
state[node].m[0] = 0;
for(auto p : adj[node]) {
int next = p[0], w = p[1];
if(next == parent) continue;
dfs(next, node);
state[next].extra_w += w;
state[next].extra_l += 1;
merge(state[node], state[next]);
}
}
int best_path(int n, int k, int h[][2], int l[]) {
n_nodes = n;
rl = k;
fr(i, 0, n - 1) {
int u = h[i][0], v = h[i][1], w = l[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(0, 0);
if(ans < infinity) return ans;
else return -1;
}
int main() {
int n, k;
cin >> n >> k;
int h[n - 1][2];
int l[n - 1];
fr(i, 0, n - 1) {
cin >> h[i][0] >> h[i][1];
}
fr(i, 0, n - 1) cin >> l[i];
cout << best_path(n, k, h, l);
return 0;
}