| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1302801 | BehruzbekX | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
int best_path (int n, int k, int h[][2], int l[]) {
vector<vector<pair<int, int>>> a(n);
for (int i = 0; i < n - 1; i++) {
a[h[i][0]].emplace_back(h[i][1], l[i]);
a[h[i][1]].emplace_back(h[i][0], l[i]);
}
int ans = INT_MAX;
vector<map<int, int>> mn(n);
vector<int> dist(n), sum(n);
auto dfs = [&] (auto &dfs, int v, int p) -> void{
mn[v][sum[v]] = dist[v];
for (auto [u, w] : a[v]) {
if (u != p) {
sum[u] = sum[v] + w;
dist[u] = dist[v] + 1;
dfs(dfs, u, v);
}
}
for (auto [u, w] : a[v]) {
int g = k + 2 * sum[u];
if (u != p) {
dfs(dfs, u, v);
if (mn[v].size() < mn[u].size()) {
swap(mn[v], mn[u]);
}
for (auto [x, y] : mn[u]) {
if (mn[v].count(g - x)) {
ans = min(ans, y + mn[v][g - x] - 2 * dist[v]);
}
}
for (auto [x, y] : mn[u]) {
if (mn[v].count(x)) {
mn[v][x] = min(mn[v][x], y);
}
else mn[v][x] = y;
}
}
}
};
dfs(dfs, 0, -1);
return (ans == INT_MAX ? -1 : ans);
}