# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1128894 | viwlesxq | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 1;
const int inf = 1e9;
int d[N], dp[N], up[N][18];
int tin[N], tout[N], timer;
vector<array<int, 2>> g[N];
void dfs(int v, int p = 0) {
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i < 18; ++i)
up[v][i] = up[up[v][i - 1]][i - 1];
for (auto [to, w] : g[v]) {
if (to != p) {
d[to] = d[v] + 1;
dp[to] = dp[v] + w;
dfs(to, v);
}
}
tout[v] = ++timer;
}
bool upper(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
if (upper(u, v)) return u;
if (upper(v, u)) return v;
for (int i = 17; i >= 0; --i)
if (!upper(up[u][i], v))
u = up[u][i];
return up[u][0];
}
int get(int u, int v, int k) {
int p = lca(u, v);
if (dp[u] + dp[v] - 2 * dp[p] == k)
return d[u] + d[v] - 2 * d[p];
return inf;
}
int best_path(int n, int k, int h[][2], int l[]) {
for (int i = 0; i < n - 1; ++i) {
g[h[i][0]].push_back({h[i][1], l[i]});
g[h[i][1]].push_back({h[i][0], l[i]});
}
dfs(0);
int res = inf;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
res = min(res, get(i, j, k));
return res < inf ? res : -1;
}