#include "factories.h"
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
const ll INF = 1000000000000000;
vector<vector<ll>> edges[500005];
ll ancc[500005][30];
ll par[500005];
ll depth[500005];
ll realdepth[500005];
ll tin[500005];
ll timer = 0;
ll anc(ll a, ll x){
if (a==0) return 0;
if (x==0) return par[a];
if (ancc[a][x] != -1) return ancc[a][x];
return ancc[a][x] = anc(anc(a, x-1), x-1);
}
ll lca(ll a, ll b){
if (depth[a] < depth[b]) swap(a,b);
FORNEG(i,19,-1) if (depth[anc(a,i)] >= depth[b]) a = anc(a,i);
if (a==b) return a;
FORNEG(i,19,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i);
return par[a];
}
void dfs(ll a, ll p, ll d, ll dd){
tin[a] = timer++;
par[a] = p;
depth[a] = d;
realdepth[a] = dd;
for (auto&i : edges[a]){
if (i[0] != p) dfs(i[0], a, d+1, dd+i[1]);
}
}
void Init(int N, int A[], int B[], int D[]) {
FOR(i,0,500005) edges[i].clear(), par[i] = -1, depth[i] = 0, realdepth[i] = -1;
FOR(i,0,500005) FOR(j,0,30) ancc[i][j] = -1;
FOR(i,0,N){
edges[A[i]].push_back({B[i], D[i]});
edges[B[i]].push_back({A[i], D[i]});
}
dfs(0, -1, 0,0);
}
ll mina[500005];
ll minb[500005];
vector<vector<ll>> vtree[500005];
void dp(ll a){
for (auto&i : vtree[a]){
dp(i[0]);
mina[a] = min(mina[a], mina[i[0]] + i[1]);
minb[a] = min(minb[a], minb[i[0]] + i[1]);
}
}
long long Query(int S, int X[], int T, int Y[]) {
vector<vector<ll>> stuff;
FOR(i,0,S) stuff.push_back({tin[X[i]],X[i]});
FOR(i,0,T) stuff.push_back({tin[Y[i]], Y[i]});
sort(stuff.begin(), stuff.end());
set<vector<ll>> stuff2;
FOR(i,1,stuff.size()){
stuff2.insert({tin[lca(stuff[i][1], stuff[i-1][1])], lca(stuff[i][1], stuff[i-1][1])});
}
if (stuff.size()){
ll temp = lca(stuff[0][1], stuff[stuff.size()-1][1]);
stuff2.insert({tin[temp], temp});
}
for (auto&i : stuff) stuff2.insert(i);
vector<ll> stack;
for (auto&i : stuff2) mina[i[1]] = INF, minb[i[1]] = INF, vtree[i[1]].clear();
FOR(i,0,S) mina[X[i]] = 0;
FOR(i,0,T) minb[Y[i]] = 0;
for (auto&i : stuff2){
while (stack.size() && )stack.pop_back();
if (stack.size()) vtree[stack[stack.size()-1]].push_back({i[1], realdepth[i[1]] - realdepth[stack[stack.size()-1]]});
stack.push_back(i[1]);
}
dp((*stuff2.begin())[1]);
ll ans = INF;
for (auto&i : stuff2) ans = min(ans, mina[i[1]] + minb[i[1]]);
return ans;
}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:6:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
76 | FOR(i,1,stuff.size()){
| ~~~~~~~~~~~~~~~~
factories.cpp:76:3: note: in expansion of macro 'FOR'
76 | FOR(i,1,stuff.size()){
| ^~~
factories.cpp:92:28: error: expected primary-expression before ')' token
92 | while (stack.size() && )stack.pop_back();
| ^
