| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1061772 | mnasser02 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef tuple<int, int, int> iii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LSOne(S) ((S) & -(S))
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
ll K;
int ans = 1e9;
void solve() {
int n;
cin >> n >> K;
vector<vii> AL(n);
vector<array<int, 3>> EL;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
EL.push_back({u, v});
}
for (int i = 0; i < n - 1; i++) {
cin >> EL[i][2];
}
for (auto [u, v, w] : EL) {
AL[u].push_back({v, w});
AL[v].push_back({u, w});
}
auto dfs = [&](auto self, int u, int p, int d, ll s) -> map<ll, int> {
map<ll, int> res;
res[s] = d;
ll targ = K + 2 * s;
for (auto [v, w] : AL[u]) {
if (v == p) continue;
auto cur = self(self, v, u, d + 1, s + w);
if (res.size() < cur.size()) swap(res, cur);
for (auto [k, v] : cur) {
if (res.count(targ - k)) ckmin(ans, v + res[targ - k] - 2 * d);
}
for (auto [k, v] : cur) {
if (res.count(k))
ckmin(res[k], v);
else
res[k] = v;
}
}
return res;
};
dfs(dfs, 0, -1, 0, 0);
cout << (ans == 1e9 ? -1 : ans) << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int tc = 1;
// cin >> tc;
while (tc--) {
solve();
}
return 0;
}