=//i_love_aisukiuwu
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/home/trucmai/.vim/tools.h"
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define debug(x...)
#endif
#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "
const int MN1 = 1e6 + 5,MN2 = 1e4 + 5,LOG = 20;
const ll MOD = 1e9 + 7,INF = 1e18;
ll tin[MN1],tout[MN1],dis[MN1],el[MN1],h[MN1],cc[MN1];
ll sptin[MN1],sptout[MN1];
pi sp[MN1][LOG];
vector<pi>adj[MN1],vt[MN1];
ll timer = 0,sptimer = 0;
void dfs(ll u,ll pre){
tin[u] = ++timer;
sp[++sptimer][0] = {h[u],u};
sptin[u] = sptimer;
for(auto [v,w] : adj[u]){
if(v == pre) continue;
dis[v] = dis[u] + w;
h[v] = h[u] + 1;
dfs(v,u);
sp[++sptimer][0] = {h[u],u};
}
tout[u] = timer;
}
ll lg_floor(ll u){return 63 - __builtin_clzll(u);}
void sparse(){
for(ll i = 1;i < LOG;++i)
for(ll j = 0;j + (1LL<<i) - 1 <= sptimer;++j)
sp[j][i] = min(sp[j][i-1],sp[j + (1LL<<(i-1))][i-1]);
}
ll lca(ll u,ll v){
ll tu = sptin[u],tv = sptin[v];
if(tu > tv) swap(tu,tv);
ll k = lg_floor(tv - tu + 1);
return min(sp[tu][k],sp[tv - (1LL<<k) + 1][k]).se;
}
pi dpfs(ll u,ll pre,ll &res){
pi short_dis = {INF,INF};
//cout << u << " " << pre << " " << res << endl;
if(cc[u] == 0) short_dis.fi = 0;
else if(cc[u] == 1) short_dis.se = 0;
for(auto [v,w] : vt[u]){
if(v == pre) continue;
pi tmp = dpfs(v,u,res);
//cout << tmp.fi << " " << tmp.se << endl;
res = min(res, min(short_dis.fi + tmp.se, short_dis.se + tmp.fi) + w);
short_dis.fi = min(short_dis.fi,tmp.fi + w);
short_dis.se = min(short_dis.se,tmp.se + w);
}
debug(u,pre,short_dis,res);
return short_dis;
}
void Init(int n, int a[],int b[],int d[]){
mset(cc,-1);
for(ll i = 0;i < n;++i){
adj[a[i]].emplace_back(b[i],d[i]);
adj[b[i]].emplace_back(a[i],d[i]);
}
dfs(0,0); sparse();
}
long long Query(int s,int x[],int t,int y[]){
vector<ll>a;
for(ll i = 0;i < s;++i){
a.emplace_back(x[i]);
cc[x[i]] = 0;
}
for(ll i = 0;i < t;++i){
a.emplace_back(y[i]);
cc[y[i]] = 1;
}
sort(all(a),[&](ll x,ll y){return tin[x] < tin[y];});
for(ll i = 0;i + 1 < s + t;++i) a.push_back(lca(a[i],a[i+1]));
sort(all(a),[&](ll x,ll y){return tin[x] < tin[y];});
a.resize(unique(all(a))-a.begin());
auto is_anc=[&](ll u,ll v)->bool{
return tin[u] <= tin[v] && tout[u] >= tin[v];
};
//create virtual tree
stack<ll>st;
auto add=[&](ll u,ll v,ll w)->void{
vt[u].emplace_back(v,w);
vt[v].emplace_back(u,w);
};
for(ll i = 0;i < a.size();++i){
while(!st.empty() && !is_anc(st.top(),a[i])) st.pop();
if(!st.empty()) add(st.top(),a[i],dis[a[i]] - dis[st.top()]);
st.push(a[i]);
}
ll res = INF;
dpfs(a[0],0,res);
for(ll i = 0;i < a.size();++i) vt[a[i]].clear();
for(ll i = 0;i < s;++i) cc[x[i]] = -1;
for(ll i = 0;i < t;++i) cc[y[i]] = -1;
return res;
}
Compilation message
factories.cpp:1:1: error: expected unqualified-id before '=' token
1 | =//i_love_aisukiuwu
| ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:111:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(ll i = 0;i < a.size();++i){
| ~~^~~~~~~~~~
factories.cpp:118:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(ll i = 0;i < a.size();++i) vt[a[i]].clear();
| ~~^~~~~~~~~~
