| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1256392 | mmmm2025 | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<array<ll, 2>> adj[200001];
map<ll, ll> fixd[200001];
ll dist[200001];
ll depth[200001];
ll dk = 0;
ll res = 1e11*2+1;
void dfs( ll v, ll pre){
fixd[v][dist[v]] = v;
for(auto x:adj[v]){
ll u = x[0];
ll w = x[1];
if(u == pre)continue;
dfs(u, v);
dist[u] = dist[v] + w;
depth[u] = depth[v] + 1;
if(fixd[u].size() > fixd[v].size()){
swap(fixd[u], fixd[v]);
}
for(auto [d, node]:fixd[u]){
if(fixd[v][d] == 0 || depth[node] < depth[fixd[v][d]]){
fixd[v][d] = node;
}
if(fixd[v][dk-d+dist[v]] != 0){
res = min(res, depth[node] + depth[fixd[v][dk-d+dist[v]]]-depth[v]);
}
}
fixd[u].clear();
}
}
ll best_path(ll n,ll k,ll h[][2],ll L[]){
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]});
}
dk = k;
res = 1e12;
for(int i = 0; i <= n; i++){
dist[i] = 0;
depth[i] = 0;
fixd[i].clear();
}
dfs(1, 0);
return res;
}