| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 683156 | LucaGreg | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define pb push_back
#define ll long long int
#define ff first
#define ss second
const ll INF = 1000000000000000000;
vector<int> adj[100010];
vector<int> weight[100010];
bool removed[100010];
int sub[100010];
int paiCentroid[100010];
pair<ll, int> minFactoryDist[100010];
int ancestor[100010][30];
ll nivel[100010];
int tin[100010], tout[100010];
int h = 0;
int t = 0;
int curQuery = 0;
void dfsInit(int cur, int pai){
sub[cur] = 1;
for(int i=0;i<(int)adj[cur].size();i++){
int viz = adj[cur][i];
if(removed[viz]) continue;
if(viz==pai) continue;
dfsInit(viz, cur);
sub[cur] += viz;
}
}
int findCentroid(int cur, int pai, int size){
for(int i=0;i<(int)adj[cur].size();i++){
int viz = adj[cur][i];
if(removed[viz]) continue;
if(viz==pai) continue;
if(sub[viz]>size/2) return findCentroid(viz, cur, size);
}
return cur;
}
void createCentroidTree(int cur, int centroidPai){
dfsInit(cur, cur);
int centroid = findCentroid(cur, cur, sub[cur]);
paiCentroid[centroid] = centroidPai;
removed[centroid] = true;
for(int i=0;i<(int)adj[centroid].size();i++){
int viz = ad[centroid][i];
if(removed[viz]) continue;
createCentroidTree(viz, centroid);
}
}
void dfs(int cur, int pai){
t++;
tin[cur] = t;
ancestor[cur][0] = pai;
for(int i=1;i<=h;i++) ancestor[cur][i] = ancestor[ancestor[cur][i-1]][i-1];
for(int i=0;i<(int)adj[cur].size();i++){
int viz = adj[cur][i];
int w = weight[cur][i];
if(viz==pai) continue;
nivel[viz] = nivel[pai] + w;
dfs(viz, cur);
}
tout[cur] = t;
}
bool isAncestor(int a, int b){
return tin[a]<=tin[b] && tout[b]<=tout[a];
}
int lca(int a, int b){
if(isAncestor(a, b)) return a;
if(isAncestor(b, a)) return b;
for(int i=h;i>=0;i--) if(!isAncestor(ancestor[a][i], b)) a = ancestor[a][i];
return ancestor[a][0];
}
ll calculaDist(int a, int b){
int lca_ = lca(a, b);
ll resp = abs(nivel[lca_] - nivel[a]) + abs(nivel[lca_] - nivel[b]);
return resp;
}
void update(int v){
int cur = v;
while(cur!=-1){
ll distancia = calculaDist(v, cur);
if(minFactoryDist[cur].ss<curQuery){
minFactoryDist[cur].ff = distancia
minFactoryDist[cur].ss = curQuery;
}else{
minFactoryDist[cur].ff = min(minFactoryDist[cur], distancia);
}
cur = paiCentroid[cur];
}
}
ll calculaMinFactoryDist(int v){
int cur = v;
ll resp = INF;
while(cur!=-1){
ll distancia = calculaDist(v, cur);
if(minFactoryDist[cur].ss<curQuery) continue;
resp = min(resp, distancia + minFactoryDist[cur].ff);
cur = paiCentroid[cur];
}
return resp;
}
void Init(int N, int A[], int B[], int D[]){
nivel[0] = 0;
dfs(0, 0);
h = ceil(log2(N));
for(int i=0;i<n-1;i++){
int a = A[i], b = B[i], d = D[i];
adj[a].pb(b);
weight[a].pb(d);
adj[b].pb(a);
weight[b].pb(d);
}
createCentroidTree(0, -1);
}
long long Query(int S, int X[], int T, int Y[]){
curQuery++;
for(int i=0;i<S;i++) update(X[i]);
ll resp = INF;
for(int i=0;i<T;i++) resp = min(resp, calculaMinFactoryDist(Y[i]));
return resp;
}