# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
383960 | wind_reaper | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int MXN = 500000;
const int LOG = 20;
const int64_t INF = 1e18;
vector<array<int, 2>> g[MXN];
int sz[MXN], centroid[MXN], up[LOG][MXN], tin[MXN], tout[MXN];
int64_t depth[MXN], best[MXN];
vector<bool> vis(MXN, 0);
int timer = 0;
void dfs(int node, int par, int dist){
tin[node] = timer++;
depth[node] = depth[par] + int64_t(dist);
up[0][node] = par;
for(int i = 1; i < LOG; i++)
up[i][node] = up[i-1][up[i-1][node]];
for(auto& [v, d] : g[node]){
if(v == par)
continue;
dfs(v, node, d);
sz[node] += sz[v];
}
tout[node] = timer;
}
inline bool isAncestor(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if(isAncestor(u, v))
return u;
if(isAncestor(v, u))
return v;
for(int i = LOG-1; i >= 0; --i){
if(!isAncestor(up[i][u], v))
u = up[i][u];
}
return up[0][u];
}
inline int64_t dist(int u, int v){
return depth[u] + depth[v] - 2*depth[lca(u, v)];
}
void decompose(int node, int c){
int inv = -1, szl = (sz[node] >> 1);
for(auto& [v, d] : g[node]){
if(!vis[v] && sz[v] > szl){
inv = v;
break;
}
}
if(inv != -1){
sz[node] -= sz[inv];
sz[inv] += sz[node];
return decompose(inv, c);
}
vis[p] = 1;
centroid[p] = c;
for(auto& [v, d] : g[node]){
if(!vis[v]){
centroid[v] = p;
decompose(v, p);
}
}
}
vector<int> hit;
void update(int node){
int v = node;
while(v != -1){
best[v] = min(best[v], dist(node, v));
hit.push_back(v);
v = centroid[v];
}
}
int64_t query(int node){
int64_t ans = INF;
int v = node;
while(v != -1){
ans = min(ans, best[v] + dist(v, node));
}
return ans;
}
void Init(int n, int A[], int B[], int D[]){
for(int i = 0; i < n; i++)
best[i] = INF;
for(int i = 0; i < n - 1; i++){
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0, 0);
decompose(0, -1);
}
long long Query(int S, int X[], int T, int Y[]){
for(int i = 0; i < S; i++)
update(X[i]);
int64_t ans = INF;
for(int i = 0; i < T; i++)
ans = min(ans, query(Y[i]));
for(int i : hit)
best[i] = INF;
hit.clear();
return ans;
}