| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 851341 | mat_jur | 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;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
int best_path(int n, ll k, int h[][2], int l[]) {
vector<vector<pair<int, int>>> G(n);
REP(i, n-1) {
G[h[i][0]].eb(mp(h[i][1], l[i]));
G[h[i][1]].eb(mp(h[i][0], l[i]));
}
vector<pair<pair<ll, ll>, map<ll, ll>>> M(n);
const int inf = 1e9;
ll res = inf;
auto merge = [&](pair<pair<ll, ll>, map<ll, ll>> a, pair<pair<ll, ll>, map<ll, ll>> b) {
if (ssize(a.se) < ssize(b.se)) swap(a, b);
for (auto x : b.se) {
ll key = x.fi+b.fi.fi;
if(a.se.find((k-key)-a.fi.fi) != a.se.end()) res = min(res, a.se[(k-key)-a.fi.fi]+a.fi.se+x.se+b.fi.se);
}
for (auto x : b.se) {
ll key = x.fi+b.fi.fi;
if (a.se.find(key-a.fi.fi) == a.se.end()) a.se[key-a.fi.fi] = inf;
a.se[key-a.fi.fi] = min(a.se[key-a.fi.fi], x.se+b.fi.se-a.fi.se);
}
return a;
};
function<void(int, int)> dfs = [&](int v, int p) {
M[v].fi.fi = M[v].fi.se = 0;
M[v].se[0] = 0;
for (auto e : G[v]) {
int u = e.fi, w = e.se;
if (u == p) continue;
dfs(u, v);
M[u].fi.fi += w;
M[u].fi.se++;
M[v] = merge(M[v], M[u]);
}
//cerr << v << '\n';
//debug(M[v]);
};
dfs(0, -1);
if (res == inf) return -1;
return int(res);
}
#ifdef LOCAL
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
int h[n-1][2];
int l[n-1];
REP(i, n-1) {
cin >> h[i][0] >> h[i][1];
}
REP(i, n-1) {
cin >> l[i];
}
cout << best_path(n, k, h, l) << '\n';
return 0;
}
#endif