#include "factories.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 2e5 + 100;
vector <pair <int, int>> ed[N];
vector <pair <int, ll>> ed2[N];
int in[N], ou[N], p[N][20], timer = 1, col[N];
ll dep[N], f1[N], f2[N];
void dfs(int u, int v) {
p[u][0] = v;
for (int j = 1; j < 20; j++)
p[u][j] = p[p[u][j - 1]][j - 1];
in[u] = ++timer;
for (auto x : ed[u]) {
if (x.f == v)
continue;
dep[x.f] = dep[u] + x.s;
dfs(x.f, u);
}
ou[u] = timer;
}
int is(int a, int b) {
return in[a] <= in[b] && ou[a] >= in[b];
}
int lca(int a, int b) {
if (is(a, b))
return a;
if (is(b, a))
return b;
for (int j = 19; j >= 0; j--) {
if (is(p[a][j], b) == 0)
a = p[a][j];
}
return p[a][0];
}
void init(int N, int A[], int B[], int D[]) {
for (int i = 1; i <= N; i++) {
f1[i] = f2[i] = 1e16;
}
for (int i = 0; i < N - 1; i++) {
A[i]++, B[i]++;
ed[A[i]].pb({B[i], D[i]});
ed[B[i]].pb({A[i], D[i]});
}
dfs(1, 1);
}
void dfs2(int u) {
if (col[u] == 1) {
f1[u] = 0;
}
if (col[u] == 2) {
f2[u] = 0;
}
for (auto x : ed2[u]) {
dfs2(x.f);
f1[u] = min(f1[u], f1[x.f] + x.s);
f2[u] = min(f2[u], f2[x.f] + x.s);
}
}
long long Query(int S, int X[], int T, int Y[]) {
vector <int> node;
for (int i = 0; i < S; i++) {
X[i]++;
node.pb(X[i]);
col[X[i]] = 2;
}
for (int i = 0; i < T; i++) {
Y[i]++;
node.pb(Y[i]);
col[Y[i]] = 1;
}
sort(all(node), [&](int a, int b) {return in[a] < in[b];});
for (int i = 0; i < S + T - 1; i++) {
node.pb({lca(node[i], node[i + 1])});
}
node.pb(1);
uniquev(node);
sort(all(node), [&] (int a, int b) {return in[a] < in[b];});
stack <int> st;
for (auto x : node) {
if (sz(st)) {
while (is(st.top(), x) == 0)
st.pop();
ed2[st.top()].pb({x, dep[x] - dep[st.top()]});
}
st.push(x);
}
dfs2(1);
ll ans = 1e16;
for (auto x : node) {
ans = min(ans, f1[x] + f2[x]);
f1[x] = f2[x] = 1e16;
col[x] = 0;
ed2[x].clear();
}
return ans;
}
Compilation message
/usr/bin/ld: /tmp/cczDg1Db.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
collect2: error: ld returned 1 exit status
