| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 79093 | gs14004 | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
typedef long long lint;
typedef pair<lint,int> pi;
vector<pi> graph[500005];
int piv, dfn[500005];
int dep[500005], sz[500005];
lint dist[500005];
int par[19][500005];
int dfs(int x, int p){
dfn[x] = ++piv;
sz[x] = 1;
for (auto &i : graph[x]){
if(p == i.second) continue;
dep[i.second] = dep[x] + 1;
dist[i.second] = dist[x] + i.first;
par[0][i.second] = x;
sz[x] += dfs(i.second, x);
}
return sz[x];
}
void Init(int N, int A[], int B[], int D[]){
for (int i=0; i<N-1; i++) {
graph[A[i]+1].push_back(pi(D[i],B[i]+1));
graph[B[i]+1].push_back(pi(D[i],A[i]+1));
}
dfs(1, 0);
for(int i=1; i<=18; i++){
for(int j=1; j<=N; j++){
par[i][j] = par[i-1][par[i-1][j]];
}
}
}
int lca(int x, int y){
if(dep[x] < dep[y]) swap(x,y);
int dx = dep[x] - dep[y];
for(int i=0; (1<<i)<=dx; i++){
if((dx >> i) & 1) x = par[i][x];
}
for (int i=18; i>=0; i--) {
if(par[i][x] != par[i][y]){
x = par[i][x];
y = par[i][y];
}
}
if(x != y) x = par[0][x];
return x;
}
bool cmp(int a, int b){
return dfn[a] < dfn[b];
}
bool sub(int a, int b){
return dfn[a] + sz[a] >= dfn[b] + sz[b];
}
vector<int> pos;
int c;
int object[500005];
lint dist[500005];
void const_g(){
vector<int> stk;
for(auto &i : pos){
if(stk.empty()) stk.push_back(i);
else{
while(!stk.empty() && !sub(stk.back(), i)) stk.pop_back();
int par = stk.back();
int cur = i;
graph[par].emplace_back(dist[cur] - dist[par], cur);
graph[cur].emplace_back(dist[cur] - dist[par], par);
stk.push_back(cur);
}
}
}
lint dijkstra(int n, int* s){
priority_queue<pi,vector<pi>,greater<pi> > pq;
for (int i=0; i<n; i++) {
pq.push(pi(0ll,s[i] + 1));
dist[s[i] + 1] = 0;
}
while (!pq.empty()) {
pi t = pq.top();
pq.pop();
if(dist[t.second] != t.first) continue;
if(object[t.second] == c) return t.first;
for(auto &i : graph[t.second]){
if(dist[i.second] > dist[x] + i.first){
dist[i.second] = dist[x] + i.first;
pq.push(pi(dist[i.second], i.second));
}
}
}
return -1;
}
lint Query(int S, int X[], int T, int Y[]){
c++;
pos.clear();
for (int i=0; i<S; i++) {
pos.push_back(X[i]+1);
}
for (int i=0; i<T; i++) {
object[Y[i]+1] = c;
pos.push_back(Y[i]+1);
}
sort(pos.begin(),pos.end(),cmp);
int p = (int)pos.size() - 1;
for (int i=0; i<p; i++) {
pos.push_back(lca(pos[i],pos[i+1]));
}
sort(pos.begin(),pos.end(),cmp);
pos.resize(unique(pos.begin(),pos.end()) - pos.begin());
for(auto &i : pos){
dist[i] = 1e18;
graph[i].clear();
}
const_g();
lint ret = dijkstra(S,X);
return ret;
}