| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 966917 | jhinezeal123 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
#define show(T) {for (auto x:T) cout<<x<<' ';cout<<endl;}
using namespace std;
const double eps = 0.0000001;
const int mod1 = 998244353,mod2 = 1e9+7,mod = 1337377;
const int N = 200005;
const int MATRIX_SIZE = 64;
int n,pa[N][20],dis[N][20],h[N],child[N],H[N][2],k,pct[N],ans=1e18,L[N];
vector <ii> G[N];
vector <int> g[N];
map <int,int> mp[N];
map <int,int>::iterator it;
bool chosen[N];
void DFS(int p,int v){
pa[v][0]=p;
h[v]=h[p]+1;
for (auto x:G[v]){
if (x.fi==p) continue;
dis[x.fi][0]=x.se;
DFS(v,x.fi);
}
}
void init(){
for (int i=1;i<=17;++i){
for (int j=1;j<=n;++j){
pa[j][i]=pa[pa[j][i-1]][i-1];
dis[j][i]=dis[j][i-1]+dis[pa[j][i-1]][i-1];
}
}
}
ii LCA(int a,int b){
ii res={0,0};
if (h[a]<h[b]) swap(a,b);
int cl=h[a]-h[b];
for (int i=log2(cl);i>=0;--i){
if (cl>=1<<i){
cl-=1<<i;
res.fi+=1<<i;
res.se+=dis[a][i];
a=pa[a][i];
}
}
if (a==b) return res;
for (int i=log2(h[a]);i>=0;--i){
if (pa[a][i]!=pa[b][i]){
res.fi+=2<<i;
res.se+=dis[a][i]+dis[b][i];
a=pa[a][i];
b=pa[b][i];
}
}
return {res.fi+2,res.se+dis[a][0]+dis[b][0]};
}
void DFS2(int p,int v){
child[v]=1;
for (auto x:G[v]){
if (x.fi==p||chosen[x.fi]) continue;
DFS2(v,x.fi);
child[v]+=child[x.fi];
}
}
int centroid(int p,int v,int sl){
for (auto x:G[v]){
if (x.fi==p||chosen[x.fi]) continue;
if (child[x.fi]-1>=sl>>1) return centroid(v,x.fi,sl);
}
return v;
}
int build(int v){
DFS2(0,v);
v=centroid(0,v,child[v]);
chosen[v]=true;
for (auto x:G[v]){
if (chosen[x.fi]) continue;
int tam=build(x.fi);
// cout<<tam<<' '<<v<<endl;
g[v].push_back(tam);
pct[tam]=v;
}
return v;
}
void up(int v,int cur){
ii tam=LCA(v,cur);
it=mp[cur].find(k-tam.se);
if (it!=mp[cur].end()) ans=min(ans,tam.fi+it->se);
it=mp[cur].emplace(tam.se,tam.fi).fi;
it->se=min(it->se,tam.fi);
if (pct[cur]) up(v,pct[cur]);
}
int best_path(int _n, int _k, int (*H)[2], int *L){
// cin>>n>>k;
n=_n;
k=_k;
for (int i=1;i<n;++i){
// cin>>H[i][0]>>H[i][1];
++H[i][0];
++H[i][1];
}
for (int i=1;i<n;++i){
// cin>>tam;
G[H[i][0]].push_back({H[i][1],L[i]});
G[H[i][1]].push_back({H[i][0],L[i]});
}
DFS(0,1);
init();
build(1);
for (int i=1;i<=n;++i) up(i,i);
return ans==1e18?-1:ans;
}