| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 975169 | aaaaaarroz | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
vector<vector<pair<long long,long long>>> graph;
// depth[u] = la profundidad de u en el arbol (la raiz tiene profundidad 0)
vector<long long> depth;
// anc[u][i] = el ancestro 2^i de u (por ejemplo, anc[u][3] = el ancestro 8 de u)
vector<vector<long long>> anc;
void dfs(long long u, long long p, long long cost){
depth[u] = depth[p] + cost; // La profundidad de u es la profundidad de su padre + 1
anc[u][0] = p; // El ancestro 2^0 de u es su padre
for(long long i = 1; i < 30; i++){ // Calculo todos los ancestros de u
anc[u][i] = anc[anc[u][i-1]][i-1];
}
for(auto [v,w] : graph[u]){ // Visito todos los hijos de u (los vecinos excepto su padre)
if(v != p){
dfs(v, u, w);
}
}
}
// Sube dist niveles desde u en el arbol
long long lift(long long u, long long dist){
for(long long i = 0; i < 30; i++){
if(dist & (1 << i)){
u = anc[u][i];
}
}
return u;
}
// Ancestro comun mas bajo de a y b
long long lca(long long a, long long b){
if(depth[a] < depth[b]) swap(a, b); // Los ordeno de tal manera que a sea el mas profundo
a = lift(a, depth[a] - depth[b]); // Subo a a la misma profundidad que b
if(a == b) return a; // Si a y b son iguales, entonces a es el lca
for(long long i = 29; i >= 0; i--){ // Subo a y b lo mas que pueda sin pasarme del lca
if(anc[a][i] != anc[b][i]){
a = anc[a][i];
b = anc[b][i];
}
}
return anc[a][0]; // El lca es el padre de a
}
void Init(long long N, long long A[], long long B[], long long D[]){
graph.resize(N,vector<pair<long long,long long>>());
depth.resize(N,0);
anc.resize(N, vector<long long>(30));
for(long long i=0;i<(N-1);i++){
graph[A[i]].push_back({B[i],D[i]});
graph[B[i]].push_back({A[i],D[i]});
}
dfs(0, 0, 0);
}
long long Query(long long S, long long X[], long long T, long long Y[]){
long long ans=LLONG_MAX;
for(int i=0;i<S;i++){
for(int j=0;j<T;j++){
ans=min(ans,(depth[X[i]]-depth[lca(X[i],Y[j])])+(depth[Y[j]]-depth[lca(X[i],Y[j])]));
}
}
return ans;
}