| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1278187 | Robert_junior | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7, mod = 1e9 + 7;
const long long N = 1e6 + 7, mod = 1e9 + 7;
long long tin[N], tout[N], d[N], d1[N], sz[N], bc[N], b[N], timer;
map<long long, long long>mn;
vector<pair<int, int>>g[N];
long long n, k;
void dfs(long long v, long long p){
sz[v] = 1;
tin[v] = ++timer;
b[tin[v]] = v;
for(auto [to, w] : g[v]){
if(to == p) continue;
d[to] = d[v] + 1;
d1[to] = d1[v] + w;
dfs(to, v);
sz[v] += sz[to];
if(sz[to] > sz[bc[v]]) bc[v] = to;
}
tout[v] = timer;
}
long long res = INT_MAX;
vector<int>cl;
void dfs1(long long v, long long p, bool keep){
for(auto [to, w] : g[v]){
if(to == p || to == bc[v]) continue;
dfs1(to, v, 0);
}
if(bc[v]) dfs1(bc[v],v, 1);
for(auto [to, w] : g[v]){
if(to == p || to == bc[v]) continue;
for(long long i = tin[to]; i <= tout[to]; i++){
long long u = b[i];
long long w = k + d1[v] * 2 - d1[u];
// d[u] + d[v] - 2 * d[lca] = k
// d[u] = k + 2 * d1[lca] -d1[v]
if(mn.find(w) != mn.end()) res = min(res, d[u] + mn[w] - 2 * d[v]);
}
for(long long i = tin[to]; i <= tout[to]; i++){
long long u = b[i];
cl.push_back(d1[u]);
mn[d1[u]] = min(mn[d1[u]], d[u]);
}
}
mn[d1[v]] = min(mn[d1[v]], d[v]);
long long w = k + d1[v];
if(mn.find(w) != mn.end()) res = min(res, mn[w] - d[v]);
cl.push_back(d1[v]);
if(!keep){
for(auto it : cl) mn[it] = 100000000;
cl.clear();
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for (int i = 0; i < n - 1; i++) {
int a = H[i][0], b = H[i][1], c = L[i];
g[a].push_back({b, c});
g[b].push_back({a, c});
}
for(int i = 0; i < n; i++){
mn[d1[i]] = 100000000;
}
dfs(0, 0);
dfs1(0, 0, 0);
if(res > n) res = -1;
return res;
}