| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1162018 | spycoderyt | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "race.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5+5;
int K;
int rem[N],sz[N],ans=1e10;
vector<pair<int,int> > A[N];
vector<int> dislist;
map<int,int>mp;
int sub_sz(int u,int par = -1) {
sz[u]=1;
for(auto [nxt,w] : A[u]) if(nxt!=par&&!rem[nxt])sz[u]+=sub_sz(nxt,u);
return sz[u];
}
int find_cen(int u,int sub_sz,int par = -1) {
for(auto [nxt,w] : A[u])if(nxt!=par&&!rem[nxt]&&2*sz[nxt] > sub_sz)return find_cen(nxt,sub_sz,u);
return u;
}
void get_cnt(int u,int par = -1,int fill = 0,int dep = 0,int dis = 0){
if(dep>K)return;
dislist.push_back(dis);
if(fill){
if(mp[dis])mp[dis] = min(mp[dis], dep);
else mp[dis] = dep;
}
else {
if(mp[K-dis])ans = min(ans,mp[K-dis]+dep);
if(dis==K)ans=min(ans,dep);
}
for(auto [nxt,w] : A[u])if(nxt!=par && !rem[nxt]) get_cnt(nxt,u,fill,dep+1,dis+w);
}
void build(int u=1) {
int cen = find_cen(u,sub_sz(u));
rem[cen]=1;
for(auto [nxt,w] : A[u]) if(!rem[nxt])get_cnt(nxt,u,0,1,w),get_cnt(nxt,u,1,1,w);
mp.clear();
for(auto [nxt,w] : A[u]) if(!rem[nxt])build(nxt);
}
int best_path(int n, int k, int h[][2], int w[])
{
K=k;
for(int i = 0;i<n-1;i++) {
int a = h[i][0], b = h[i][1];
A[a].push_back({b,w[i]});
A[b].push_back({a,w[i]});
}
build();
if(ans>=1e9)return -1;
else return ans;
}