| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 364633 | 2021-02-09T15:30:42 Z | bigDuck | Factories (JOI14_factories) | C++14 | 0 ms | 0 KB |
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
int anc[500010][21];
vector<pii> g[500010];
int d[500010];
int tmp=0;
int ent[500010], ex[500010];
int n;
void dfs(int s){
tmp++;
ent[s]=tmp;
for(pii pr:g[s]){
int u=pr.ft, c=pr.sc;
if(u==anc[s][0]){continue;}
d[u]=d[s]+c;
anc[u][0]=s;
dfs(u);
}
tmp++;
ex[s]=tmp;
return;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=0; i<(n-1); i++){
g[A[i]+1 ].pb({B[i]+1, D[i]});
g[B[i]+1 ].pb({A[i]+1, D[i]});
}
dfs(1);
for(int i=1; i<=20; i++){
for(int j=1; j<=n; j++){
anc[j][i]=anc[anc[j][i-1] ][i-1];
}
}
return;
}
bool is_anc(int u, int v){
return (ent[u]<=ent[v]) && (ex[u]>=ex[v]);
}
int lca(int u, int v){
if( is_anc(u, v) ){
return u;
}
int cr=u;
for(int i=20; i>=0; i--){
if( (anc[cr][i]!=(0)) && (!is_anc(anc[cr][i], v)) ){
cr=anc[cr][i];
}
}
return anc[cr][0];
}
long long Query(int S, int X[], int T, int Y[]) {
int res=1e18;
for(int i=0; i<S; i++){
for(int j=0; j<T; j++){
int u=X[i]+1, v=Y[j]+1;
int anc=lca(u, v);
res=min(res, d[u]+d[v]-2*d[anc]);
}
}
return res;
}