#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int L = 19;
struct node {
vector<pair<node*,int>> l;
long long d;
int depth;
node* anc[L];
node* par;
bool v = false;
int sz;
long long cl = LONG_LONG_MAX;
};
node* lca(node* u, node* v){
if(u->depth < v->depth) swap(u, v);
int d = u->depth-v->depth;
for(int i = 0;i < L;i++) if((d>>i)&1) u = u->anc[i];
if(u == v) return u;
for(int i = L-1;i >= 0;i--){
if(u->anc[i] != v->anc[i]) {
u = u->anc[i];
v = v->anc[i];
}
}
return u->anc[0];
}
int tot;
void ffs(node* n, node* p, long long d, int depth){
n->d = d;
n->depth = depth;
n->anc[0] = p;
for(int i = 1;i < L;i++) n->anc[i] = n->anc[i-1]->anc[i-1];
for(auto [c, l] : n->l){
if(c != p) ffs(c, n, d+l, depth+1);
}
}
void dfs(node* n, node* p){
n->sz = 1;
for(auto [c, d] : n->l){
if(c == p || c->v) continue;
dfs(c, n);
n->sz += c->sz;
}
}
node* cent(node* n, node* p){
for(auto [c,d]:n->l){
if(c==p||c->v) continue;
if(c->sz>tot/2){
return cent(c, n);
}
}
n->v = true;
for(auto [c,d] : n->l){
if(c->v) continue;
dfs(c, n);
tot = c->sz;
node* ce = cent(c, n);
ce->par = n;
}
return n;
}
vector<node> g;
void Init(int N, int A[], int B[], int D[]) {
g.resize(N);
for(int i = 0;i < N-1;i++){
g[A[i]].l.emplace_back(&g[B[i]], D[i]);
g[B[i]].l.emplace_back(&g[A[i]], D[i]);
}
tot = N;
ffs(&g[0], &g[0], 0, 0);
dfs(&g[0], NULL);
cent(&g[0], NULL)->par = NULL;
}
long long Query(int S, int X[], int T, int Y[]) {
vector<node*> t;
#pragma GCC ivdep
for(int i = 0;i < S;i++){
node* x = &g[X[i]];
while(x != NULL){
t.push_back(x);
x->cl = min(x->cl, x->d+g[X[i]].d-2*lca(&g[X[i]], x)->d);
x = x->par;
}
}
#pragma GCC ivdep
long long ans = LONG_LONG_MAX;
for(int i = 0;i < T;i++){
node* y = &g[Y[i]];
while(y != NULL){
if(y->cl != LONG_LONG_MAX) ans = min(ans, y->d+g[Y[i]].d-2*lca(&g[Y[i]], y)->d+y->cl);
y = y->par;
}
}
for(node* n : t) n->cl = LONG_LONG_MAX;
return ans;
}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:89:3: error: for, while or do statement expected before 'long'
89 | long long ans = LONG_LONG_MAX;
| ^~~~
