이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
int best_path(int n, int k, int h[][2], int l[]) {
vector<vector<pii>> adj(n);
for (int i = 0; i < n - 1; i++) {
adj[h[i][0]].push_back({h[i][1], l[i]});
adj[h[i][1]].push_back({h[i][0], l[i]});
}
vector<ll> f(n);
vector<int> dep(n);
const auto build = [&](int u, int p, auto &&self) -> void {
for (auto [v, w] : adj[u]) {
if (v == p) { continue; }
f[v] = f[u] + w;
dep[v] = dep[u] + 1;
self(v, u, self);
}
};
build(0, -1, build);
vector<map<ll, int>> mp(n);
const int INF = 1e9;
int res = INF;
const auto merge = [&](int i, int j) -> void {
if (mp[j].count(f[i] + k)) {
res = min(res, mp[j][f[i] + k] - dep[i]);
}
ll need = k + f[i] * 2;
int sub = 2 * dep[i];
if (sz(mp[i]) < sz(mp[j])) {
swap(mp[i], mp[j]);
}
for (auto [len, dx] : mp[j]) {
if (mp[i].count(need - len)) {
res = min(res, dx + mp[i][need - len] - sub);
}
}
for (auto [len, dx] : mp[j]) {
if (mp[i].count(len)) {
mp[i][len] = min(mp[i][len], dx);
} else {
mp[i][len] = dx;
}
}
};
const auto dfs = [&](int u, int p, auto &&self) -> void {
for (auto [v, w] : adj[u]) {
if (v == p) { continue; }
self(v, u, self);
merge(u, v);
}
mp[u][f[u]] = dep[u];
};
dfs(0, -1, dfs);
return res < INF ? res : -1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |