#include "factories.h"
#include <vector>
template<typename T> bool ckmax(T& a, T b){return a<b?a=b,1:0;}
template<typename T> bool ckmin(T& a, T b){return b<a?a=b,1:0;}
using ll = long long;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MN = 5e5+10;
struct edge{public: int n,w;};
std::vector<edge> a[MN];
struct group{public: int c;ll d;};
std::vector<group> g[MN];
int s[MN];
bool r[MN];
ll ans, bt[MN], bs[MN];
int dfs(int n, int p=-1)
{
s[n]=1;
for(auto x:a[n])
if(!r[x.n]&&x.n!=p)
s[n]+=dfs(x.n, n);
return s[n];
}
int get_centroid(int n, int ms, int p=-1)
{
for(auto x:a[n])
if(!r[x.n]&&x.n!=p)
if(s[x.n]*2>=ms)
return get_centroid(x.n, ms, n);
return n;
}
int top;
void dfs2(int n, int p=-1, ll d=0)
{
g[n].push_back({top, d});
for(auto x:a[n])
if(x.n!=p)
dfs2(x.n, n, d+x.w);
}
void work(int n)
{
int c=get_centroid(n, dfs(n));
top=c;
dfs2(c);
r[c]=1;
for(auto x:a[c])
if(!r[x.n])
work(x.n);
}
void Init(int N, int A[], int B[], int D[])
{
for(int i=0;i+1<N;++i)
a[A[i]].push_back({B[i], D[i]}), a[B[i]].push_back({A[i], D[i]});
work(0);
memset(bs, 0x3f, sizeof bs);
memset(bt, 0x3f, sizeof bt);
}
long long Query(int S, int X[], int T, int Y[])
{
ans=INF;
for(int i=0;i<S;++i)
for(auto x:g[X[i]])
ckmin(bs[x.c], x.d);
for(int i=0;i<T;++i)
for(auto x:g[Y[i]])
ckmin(bt[x.c], x.d), ckmin(ans, bs[x.c]+bt[x.c]);
for(int i=0;i<S;++i)
for(auto x:g[X[i]])
bs[x.c]=bt[x.c]=INF;
for(int i=0;i<T;++i)
for(auto x:g[Y[i]])
bs[x.c]=bt[x.c]=INF;
return ans;
}
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:60:2: error: 'memset' was not declared in this scope
memset(bs, 0x3f, sizeof bs);
^~~~~~
