| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 700990 | angelo_torres | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "factories.h"
#define ff first
#define ss second
using namespace std;
typedef long long ll;
const ll N = 5e5 + 10;
const ll M = 2e6 + 20;
const ll inf = 1e17;
int n,t[N],p[N];
ll d[N],q[N];
vector<pair<int,ll>> g[N];
deque<ll> s[N];
void dfs(int v,int f){
t[v] = 1;
for(auto [u,w] : g[v]){
if(u == f) continue;
dfs(u,v);
t[v] += t[u];
}
}
int find(int v,int f,int tm){
for(auto [u,w] : g[v]){
if(u == f) continue;
if(t[u]*2 > tm) return find(u,v,tm);
}
return v;
}
void gfs(int v,int f){
s[v].push_front(d[v]);
for(auto [u,w] : g[v]){
if(u == f) continue;
d[u] = d[v] + w;
gfs(u,v);
}
}
void build(int v,int f){
dfs(v,f);
int c = find(v,f,t[v]);
d[v] = 0, p[c] = f;
gfs(v,f);
for(auto [u,w] : g[c]){
if(u == f) continue;
build(u,c);
}
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(int i = 0; i < n; ++i){
g[A[i]].push_back({B[i],(ll) D[i]});
g[B[i]].push_back({A[i],(ll) D[i]});
}
build(0,-1);
}
long long Query(int S, int X[], int T, int Y[]){
for(int i = 0; i < S; ++i){
int aux = X[i], id = 0;
while(aux != -1){
q[aux] = min(q[aux],s[x[i]][id]);
aux = p[aux], id++;
}
}
ll ans = inf;
for(int i = 0; i < T; ++i){
int aux = Y[i], id = 0;
while(aux != -1){
ans = min(ans,q[aux]+s[y[i]][id]);
aux = p[aux], id++;
}
}
for(int i = 0; i < S; ++i){
int aux = x[i];
while(aux != -1) q[aux] = inf, aux = p[aux];
}
return ans;
}