| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 532292 | Pietra | 공장들 (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// tem uma arvore
// cada companhia produz uma materia smp dif - cada uma tem no minimo
// uma industria, essa ficam nos vertices
// pode ter mais de uma industria numa msm cidade
// as vzs uma precisa de material da outra
// queremos minimizar a dist a ser percorrida ao precisar de uma materia da ind G
// query: a companhia u (com empresas em x1, x2,...) precisa
// de material da companhia v (com empresas em y1, y2, ...)
// qual a menor dist?
// lca + centroid
// pega de um centroid p outro
// guarda o mais prox e p subir do vertice p centroide e de um p outro
// usa o lca pra pegar a dist
// atualiza o centroid p cada empresa q lê
// vendo se ela cria um novo caminho minimo
// pega o min entre oq ja ta e o min entre o vertice ate o cara k (centroid)
// na query queremos o minimo de ir ate o centroid atual e a menor
// dist q ele tem pra algm empresa A
#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6 + 5 ;
const ll inf = 1e18 ;
const int maxl = 21 ;
int tab[maxl][maxn], nivel[maxn], cent[maxn] ;
long long dist[maxn], resp[maxn] ;
int sz[maxn], pai[maxn], timer ;
bitset<maxn> vis[maxn] ;
int tin[maxn], tout[maxn] ;
vector<pair<int,int>> grafo[maxn] ;
bool anc(int a, int b){
// b em a
return (tin[a] <= tin[b] && tout[a] >= tout[b]) ;
}
int lca(int u, int v){
if(anc(u, v)) return u ;
if(anc(v, u)) return v ;
if(tin[u] < tin[v]) swap(u, v) ;
for(int i = maxl - 1 ; i >= 0 ; i--){
if(!anc(tab[i][v], u) && tab[i][v]) v = tab[i][v] ;
}
return tab[0][v] ;
}
ll find_dist(int a, int b){
return dist[a] + dist[b] - ((dist[lca(a, b)])<<1) ;
}
void update_cent(int u){
int k = u ;
while(k){
resp[k] = min(resp[k], find_dist(u, k)) ;
k = pai[k] ;
}
}
void ini(int u){
int k = u ;
while(k){
resp[k] = inf ; k = pai[k] ;
}
}
ll query(int x){
int k = x ; ll ans = inf ;
while(k){
ans = min(ans, find_dist(x, k) + resp[k]) ;
k = pai[k] ;
}
return ans ;
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = inf ;
for(int i = 0 ; i < S ; i++) update_cent(X[i] + 1) ;
for(int i = 0 ; i < T ; i++) ans = min(ans, query(Y[i] + 1)) ;
for(int i = 0 ; i < S ; i++) ini(X[i] + 1) ;
return ans ;
}
void dfs_cent(int v, int p){
sz[v] = 1 ;
for(auto a : grafo[v]){
if(cent[a.first] || a.first == p) continue ;
dfs_cent(a.first, v) ;
sz[v] += sz[a.first] ;
}
}
int find_cent(int v, int p, int szz){
for(auto a : grafo[v]){
if(a.first == p || cent[a.first] || sz[a.first]*2 <= szz) continue ;
return find_cent(a.first, v, szz) ;
}
return v ;
}
void make_cent(int v, int p){
dfs_cent(v, p) ;
int c = find_cent(v, p, sz[v]) ;
cent[c] = 1, pai[c] = p ;
for(auto a : grafo[c]){
if(cent[a.first]) continue ;
make_cent(a.first, c) ;
}
}
void dfs(int v, int p){
vis[v] = 1 ;
tab[0][v] = p ;
tin[v] = ++timer ;
for(int i = 1 ; i < maxl ; i++) tab[i][v] = tab[i-1][tab[i-1][v]] ;
for(auto a : grafo[v]){
if(vis[a.first] || a.first == p) continue ;
dist[a.first] = dist[v] + a.second ;
dfs(a.first, v) ;
}
tout[v] = ++timer ;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0 ; i < N - 1 ; i++){
grafo[A[i]+1].push_back({B[i]+1, D[i]}) ;
grafo[B[i]+1].push_back({A[i]+1, D[i]}) ;
}
dfs(1, 0) ; make_cent(1, 0) ;
for(int i = 0 ; i < N + 1 ; i++) resp[i] = inf ;
}