| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1304521 | disfyy | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 500005;
const ll INF = (ll)2e18;
ll up[N][23], dp[N], sum[N][23];
ll tin[N], tout[N], timer;
vector<pair<ll,ll>> g[N];
void dfs(ll v, ll p) {
dp[v] = dp[p] + 1;
tin[v] = ++timer;
for (int i = 1; i <= 22; i++) {
up[v][i] = up[ up[v][i-1] ][i-1];
sum[v][i] = sum[v][i-1] + sum[ up[v][i-1] ][i-1];
}
for (auto it : g[v]) {
ll to = it.first;
ll w = it.second;
if (to != p) {
up[to][0] = v;
sum[to][0] = w;
dfs(to, v);
}
}
tout[v] = timer;
}
bool check(ll u, ll v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
ll lca(ll u, ll v) {
if (check(u, v)) return u;
if (check(v, u)) return v;
for (int i = 22; i >= 0; i--) {
if (!check(up[u][i], v))
u = up[u][i];
}
return up[u][0];
}
ll calc(ll u, ll need) {
ll ans = 0;
for (int i = 22; i >= 0; i--) {
if (need & (1LL << i)) {
ans += sum[u][i];
u = up[u][i];
}
}
return ans;
}
int best_path(int N, int K, vector<vector<int>> H, vector<int> L) {
for (int i = 0; i < N - 1; i++) {
ll u = H[i][0] + 1;
ll v = H[i][1] + 1;
ll w = L[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
up[1][0] = 1;
dfs(1, 0);
ll mn = INF;
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
ll r = lca(i, j);
ll dist = calc(i, dp[i] - dp[r]) + calc(j, dp[j] - dp[r]);
if (dist == K) {
mn = min(mn, dp[i] + dp[j] - 2 * dp[r]);
}
}
}
if (mn == INF) return -1;
return (int)mn;
}