| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 766564 | Mahmoud_Atia | 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>
typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0};
int dj[] = {0, 1, 0, -1};
const ll oo = 1e18, MOD = 1e9 + 7;
const int N = 1e6 + 5, M = 1e6 + 5;
const ld PI = acos(-1.0), EPS = 1e-9;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int t, n, m, k, a[N], sz[N], tmp[N], mx, l[N], r[N];
vector<pair<int, int>> v[N];
bool vis[N];
int ans = 1e9;
int get_subtree_sizes(int node, int p = -1) {
sz[node] = 1;
for (auto x:v[node]) if (x.first != p && !vis[x.first]) sz[node] += get_subtree_sizes(x.first, node);
return sz[node];
}
int get_centroid(int node, int size, int p = -1) {
for (auto x:v[node]) {
if (x.first == p || vis[x.first]) continue;
if (sz[x.first] >= size) return get_centroid(x.first, size, node);
}
return node;
}
bool y;
void get_cnt(int node, int p, int yes, int sum, int level) {
if (sum > k) return;
if (sum == k) ans = min(ans, level);
if (yes == 1) tmp[sum] = min(tmp[sum], level);
else if (yes) tmp[sum] = 1e9;
else ans = min(ans, level + tmp[k - sum]);
for (auto x:v[node]) if (x.first != p && !vis[x.first]) get_cnt(x.first, node, yes, sum + x.second, level + 1);
}
void centroid_decomp(int node = 0) {
get_subtree_sizes(node);
int c = get_centroid(node, sz[node] / 2);
vis[c] = 1;
if (c == 6) y = 1;
else y = 0;
mx = 0;
for (auto x:v[c]) if (!vis[x.first]) get_cnt(x.first, c, 0, x.second, 1), get_cnt(x.first, c, 1, x.second, 1);
for (auto x:v[c]) if (!vis[x.first]) get_cnt(x.first, c, 2, x.second, 1);
for (auto x:v[c]) if (!vis[x.first]) centroid_decomp(x.first);
}
//#define endl '\n'
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("marsllino.in", "r", stdin);
//memset(dp, -1, sizeof dp);
fill(tmp, tmp + N, 1e9);
cin >> n >> k;
for (int i = 1; i < n; i++) cin >> l[i] >> r[i];
for (int i = 1; i < n; i++) {
cin >> m;
v[l[i]].push_back({r[i], m});
v[r[i]].push_back({l[i], m});
}
centroid_decomp();
cout << (ans == 1e9 ? -1 : ans);
return 0;
}