| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 555413 | Dan4Life | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100;
int jmp[maxn][25], dis[maxn], depth[maxn], subtree[maxn], par[maxn], vis[maxn];
set<pair<int,int>> adj[maxn];
multiset<pair<int,int>> S[maxn];
map<pair<int,int>,int> M;
void dfs(int s, int p, int ok){
subtree[s]=1;
if(ok){
depth[s] = (p==-1?0:depth[p]+1);
dis[s] = (p==-1?0:dis[p]+M[{p,s}]);
jmp[s][0] = p;
}
for(auto x : adj[s]){
int u = x.first;
if(u==p) continue;
dfs(u,s,ok), subtree[s]+=subtree[u];
}
}
int find_centroid(int s, int p, int sz){
for(auto u : adj[s])
if(u.first!=p and subtree[u.first]>sz/2)
return find_centroid(u.first, s, sz);
return s;
}
void make_centroid(int s, int p){
dfs(s,-1,0); int sz = subtree[s];
int centroid = find_centroid(s,-1,sz);
par[centroid]=p;
while(!adj[centroid].empty()){
int x = adj[centroid].begin()->first;
adj[x].erase(adj[x].lower_bound({centroid,-1}));
adj[centroid].erase(adj[centroid].begin());
make_centroid(x,centroid);
}
}
int get_path(int x, int k){
for(int j = 0; j <= 20; j++)
if(k&(1ll<<j) and x!=-1) x = jmp[x][j];
return x;
}
int lca(int a, int b){
if(a==b) return a;
if(jmp[a][0]==jmp[b][0]) return jmp[a][0];
if(depth[a]>depth[b]) swap(a,b);
if(depth[a]<depth[b]) return lca(a,get_path(b,depth[b]-depth[a]));
for(int j = 20; j >= 0; j--)
if(jmp[a][j]!=-1 and jmp[a][j]!=jmp[b][j])
return lca(jmp[a][j], jmp[b][j]);
}
int dist(int a, int b){
return dis[a]+dis[b]-2*dis[lca(a,b)];
}
int len(int a, int b){
return depth[a]+depth[b]-2*depth[lca(a,b)];
}
int best_path(int N, int K, int H[][2], int L[])
{
int ans = N+1;
for(int i = 0; i < N-1; i++)
adj[++H[i][0]].insert({++H[i][1],L[i]}),
adj[H[i][1]].insert({H[i][0],L[i]}),
M[{H[i][0],H[i][1]}]=M[{H[i][1],H[i][0]}]=L[i];
memset(jmp, -1, sizeof(jmp));
dfs(1,-1,1); make_centroid(1,-1);
for(int j = 1; j <= 20; j++)
for(int i = 1; i <= N; i++)
if(jmp[i][j-1]!=-1) jmp[i][j] = jmp[jmp[i][j-1]][j-1];
for(int i = 1; i <= N; i++){
int x = i;
while(x!=-1){
S[x].insert({dist(i,x),len(i,x)});
x = par[x];
}
}
for(int i = 1; i <= N; i++){
if(vis[i]) continue;
int x = i; vector<int> v; v.clear();
while(x!=-1){
for(auto u : v) S[x].erase(S[x].find({dist(x,u),len(x,u)}));
v.push_back(x), x = par[x];
}
for(auto u : v){
x = u; vis[u]=1;
while(x!=-1){
int D = dist(x,u);
auto itr = S[x].lower_bound({K-D,-1});
if(itr!=S[x].end() and itr->first==K-D)
ans = min(ans, len(x,u)+itr->second);
x = par[x];
}
}
x = i;
while(x!=-1){
for(auto u : v) S[x].insert({dist(x,u),len(x,u)});
x = par[x];
}
}
return (ans==N+1?-1:ans);
}