#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define file "input"
void setIO() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(file".inp", "r")) {
freopen(file".inp", "r", stdin);
freopen(file".out", "w", stdout);
}
}
const int N = 5e5+5, LOG = 19;
int n, q;
vector<ii> graph[N];
int cnt, anc[N][LOG], st[N], en[N];
ll distb[N], distr[N], curpar[N], wei[N];
vector<int> node;
bool red[N], blue[N];
void dfs_prep(int u, int p) {
anc[u][0] = p;
foru(i, 1, LOG-1) anc[u][i] = anc[anc[u][i-1]][i-1];
st[u] = ++cnt;
fore(x, graph[u]) if (x.first != p) {
wei[x.first] = wei[u] + x.second;
dfs_prep(x.first, u);
}
en[u] = cnt;
}
bool isanc(int u, int v) {
return st[u] <= st[v] && en[v] <= en[u];
}
int lca(int u, int v) {
if (isanc(u, v)) return u;
ford(i, LOG-1, 0) {
int tmp = anc[u][i];
if (!isanc(tmp, v)) u = tmp;
}
return anc[u][0];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
foru(i, 0, n-2) {
graph[A[i]+1].emplace_back(B[i]+1, D[i]);
graph[B[i]+1].emplace_back(A[i]+1, D[i]);
}
en[0] = n+1;
prep_dfs(1, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
foru(i, 0, S-1) {
int v = X[i];
cin >> v; ++v;
node.push_back(v);
red[v] = 1;
}
foru(i, 0, T-1) {
int v = Y[i];
cin >> v; ++v;
node.push_back(v);
blue[v] = 1;
}
sort(all(node), [&](int x, int y){
return st[x] < st[y];
});
int m = sz(node)-2;
foru(i, 0, m) node.push_back(lca(node[i], node[i+1]));
sort(all(node), [&](int x, int y){
return st[x] < st[y];
});
node.resize(unique(all(node)) - node.begin());
stack<int> tmp;
fore(u, node) {
distb[u] = distr[u] = N;
curpar[u] = 0;
while (!tmp.empty()) {
if (en[tmp.top()] < st[u]) tmp.pop();
else {
curpar[u] = tmp.top();
break;
}
}
tmp.push(u);
}
ll ans = N;
ford(i, sz(node)-1, 0) {
int u = node[i];
if (blue[u]) distb[u] = 0;
if (red[u]) distr[u] = 0;
ans = min(ans, distb[u] + distr[u]);
if (curpar[u] > 0) {
distb[curpar[u]] = min(distb[curpar[u]], distb[u] + wei[u] - wei[curpar[u]]);
distr[curpar[u]] = min(distr[curpar[u]], distr[u] + wei[u] - wei[curpar[u]]);
}
}
fore(u, node) {
blue[u] = red[u] = 0;
}
node.clear();
return ans;
}
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:65:3: error: 'prep_dfs' was not declared in this scope
65 | prep_dfs(1, 0);
| ^~~~~~~~
factories.cpp: In function 'void setIO()':
factories.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen(file".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen(file".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
