| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 238698 | T0p_ | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define N 200002
#define pb push_back
struct EDGE
{
int node, weight;
};
int ans = 1e9, K;
int lv[N], jmp[2][20][N], sz[N];
bool visit[N];
map<int, int> mp[N];
vector<EDGE> g[N];
void dfs(int u, int l)
{
lv[u] = l;
for(auto x : g[u])
{
if(lv[x.node]) continue ;
dfs(x.node, l+1);
jmp[0][0][x.node] = u;
jmp[1][0][x.node] = x.weight;
}
}
int get_sz(int u, int p)
{
sz[u] = 1;
for(auto x : g[u])
{
if(visit[x.node] || x.node == p) continue ;
sz[u] += get_sz(x.node, u);
}
return sz[u];
}
int get_centroid(int u, int p, int n)
{
bool ch = (n - sz[u] <= n/2) ? true : false;
int nn = 0, nf = 0;
for(auto x : g[u])
{
if(visit[x.node] || x.node == p) continue ;
if(sz[x.node] > n/2)
{
ch = false;
if(sz[x.node] > nf)
{
nn = x.node;
nf = sz[x.node];
}
}
}
return (ch) ? u : get_centroid(nn, u, n);
}
pair<int, int> finddis(int u, int v)
{
int r1 = 0, r2 = 0;
if(lv[u] < lv[v]) swap(u, v);
for(int i=19 ; i>=0 ; i--)
if(lv[jmp[0][i][u]] >= lv[v])
{
r1 += (1<<i);
r2 += jmp[1][i][u];
u = jmp[0][i][u];
}
if(u == v) return {r1, r2};
for(int i=19 ; i>=0 ; i--)
if(jmp[0][i][u] != jmp[0][i][v])
{
r1 += (1<<(i+1));
r2 += jmp[1][i][u] + jmp[1][i][v];
u = jmp[0][i][u], v = jmp[0][i][v];
}
return {r1+2, r2+jmp[1][0][u]+jmp[1][0][v]};
}
void compute(int u, int p, int r)
{
pair<int, int> dis = finddis(u, r);
if(dis.second == K) ans = min(ans, dis.first);
else if(mp[r].count(K - dis.second)) ans = min(ans, mp[r][K - dis.second] + dis.first);
for(auto x : g[u])
{
if(visit[x.node] || x.node == p) continue ;
compute(x.node, u, r);
}
}
void update(int u, int p, int r)
{
pair<int, int> dis = finddis(u, r);
if(mp[r].count(dis.second)) mp[r][dis.second] = min(mp[r][dis.second], dis.first);
else mp[r][dis.second] = dis.first;
for(auto x : g[u])
{
if(visit[x.node] || x.node == p) continue ;
update(x.node, u, r);
}
}
void build(int u, int p)
{
int c = get_centroid(u, p, get_sz(u, p));
visit[c] = true;
t for(auto x : g[c])
{
if(visit[x.node]) continue ;
compute(x.node, c, c);
update(x.node, c, c);
}
for(auto x : g[c])
{
if(visit[x.node]) continue ;
build(x.node, c);
}
}
int best_path(int n, int k, int h[][2], int l[])
{
K = k;
for(int i=0 ; i<n-1 ; i++)
{
g[h[i][0]+1].pb({h[i][1]+1, l[i]});
g[h[i][1]+1].pb({h[i][0]+1, l[i]});
}
dfs(1, 1);
for(int i=1 ; i<20 ; i++)
for(int j=1 ; j<=n ; j++)
{
jmp[0][i][j] = jmp[0][i-1][jmp[0][i-1][j]];
jmp[1][i][j] = jmp[1][i-1][j] + jmp[1][i-1][jmp[0][i-1][j]];
}
build(1, 0);
return (ans == 1e9) ? -1 : ans;
}