#include "factories.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct edg{
int v;
long long w;
};
vector<edg>g[500009];
vector<edg>lon[500009];
long long dis[500009];
int dep[500009];
int st[500009][21];
int sub[500009];
int use[500009];
int in[500009];
int use[500009];
int ck[500009];
int cnt=0;
bool cmp(int i,int j){
return in[i]<in[j];
}
void dfs(int u,int par){
in[u]=++cnt;
for (auto v:g[u]){
if (v.v==par)continue;
dis[v.v]=v.w+dis[u];
dep[v.v]=dep[u]+1;
st[v.v][0]=u;
dfs(v.v,u);
}
}
inline int lca(int u,int v){
if (dep[u]<dep[v])swap(u,v);
int k=dep[u]-dep[v];
for (int i=18;i>=0;i--){
if (k>>i&1){
u=st[u][i];
}
}
if (u==v)return u;
for (int i=18;i>=0;i--){
if (st[u][i]==0||st[v][i]==0)continue;
if (st[u][i]!=st[v][i]){
u=st[u][i];
v=st[v][i];
}
}
return st[u][0];
}
inline long long cal(int u,int v){
return dis[u]+dis[v]-2*dis[lca(u,v)];
}
long long cac[500009];//min 1
long long buoi[500009];//min 2
void Init(int n,int a[],int b[],int d[]){
for (int i=0;i<n-1;i++){
a[i]++;
b[i]++;
g[a[i]].push_back({b[i],d[i]});
g[b[i]].push_back({a[i],d[i]});
}
dfs(1,0);
for (int i=1;i<=18;i++){
for (int j=1;j<=n;j++){
cac[j]=buoi[j]=1e17;
st[j][i]=st[st[j][i-1]][i-1];
}
}
}
long long ans=1e17;
void redfs(int u){
if (use[u]==1)cac[u]=0;
if (use[u]==2)buoi[u]=0;
for (auto v:lon[u]){
redfs(v.v);
cac[u]=min(cac[u],cac[v.v]+v.w);
buoi[u]=min(buoi[u],buoi[v.v]+v.w);
}
ans=min(ans,cac[u]+buoi[u]);
}
long long Query(int s,int x[],int t,int y[]){
vector<int>tp;
for (int i=0;i<s;i++){
use[x[i]+1]=1;
ck[x[i]+1]=1;
tp.push_back(x[i]+1);
}
for (int i=0;i<t;i++){
use[y[i]+1]=2;
ck[y[i]+1]=1;
tp.push_back(y[i]+1);
}
sort(tp.begin(),tp.end(),cmp);
for (int i=1;i<(int)tp.size();i++){
int u=tp[i],v=tp[i-1];
if (ck[lca(u,v)]==0){
ck[lca(u,v)]=1;
tp.push_back(lca(u,v));
}
}
sort(tp.begin(),tp.end(),cmp);
vector<int>dit;
for (auto v:tp){
if (!dit.empty()){
dit.push_back(v);
}
else {
while (lca(dit.back(),v)!=dit.back())dit.pop_back();
lon[dit.back()].push_back({v,cal(dit.back(),v)});
dit.push_back(v);
}
}
ans=1e17;
redfs(dit.begin());
for (auto v:tp){
ck[v]=0;
lon[v].clear();
cac[v]=buoi[v]=1e17;
}
for (int i=0;i<s;i++){
use[x[i]+1]=0;
}
for (int i=0;i<t;i++){
use[t[i]+1]=0;
}
return ans;
}
Compilation message
factories.cpp:18:5: error: redefinition of 'int use [500009]'
18 | int use[500009];
| ^~~
factories.cpp:16:5: note: 'int use [500009]' previously declared here
16 | int use[500009];
| ^~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:116:16: error: cannot convert 'std::vector<int>::iterator' to 'int'
116 | redfs(dit.begin());
| ~~~~~~~~~^~
| |
| std::vector<int>::iterator
factories.cpp:73:16: note: initializing argument 1 of 'void redfs(int)'
73 | void redfs(int u){
| ~~~~^
factories.cpp:126:10: error: invalid types 'int[int]' for array subscript
126 | use[t[i]+1]=0;
| ^
