#include "werewolf.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 1e6 + 7;
int p1[N], jump1[N], time1[N], l1[N], r1[N];
int st1[N][20];
vi T1[N];
int find1(int u) {
return jump1[u] == u ? u : jump1[u] = find1(jump1[u]);
}
int p2[N], jump2[N], time2[N], l2[N], r2[N];
vi T2[N];
int st2[N][20];
int find2(int u) {
return jump2[u] == u ? u : jump2[u] = find2(jump2[u]);
}
vi check_validity(int n, vi a, vi b, vi S, vi E, vi L, vi R) {
int m = SZ(a), q = SZ(S);
V<vi> G(n);
for(int i = 0; i < m; i++) {
G[a[i]].PB(b[i]);
G[b[i]].PB(a[i]);
}
int rt1, rt2;
{
int cnt = n;
for(int i = 0; i < n; i++) {
time1[i] = jump1[i] = p1[i] = i;
for(int j:G[i]) if(j < i) {
int x = find1(j), y = find1(i);
if(x == y) continue;
jump1[x] = jump1[y] = p1[x] = p1[y] = cnt;
T1[cnt].PB(x), T1[cnt].PB(y);
p1[cnt] = jump1[cnt] = cnt;
time1[cnt] = i;
cnt++;
}
}
rt1 = cnt - 1;
for(int i = 0; i < cnt; i++)
st1[i][0] = p1[i];
for(int j = 1; j < 20; j++)
for(int i = 0; i < cnt; i++)
st1[i][j] = st1[st1[i][j - 1]][j - 1];
}
{
int cnt = n;
for(int i = n - 1; i >= 0; i--) {
time2[i] = jump2[i] = p2[i] = i;
for(int j:G[i]) if(j > i) {
int x = find2(j), y = find2(i);
if(x == y) continue;
jump2[x] = jump2[y] = p2[x] = p2[y] = cnt;
T2[cnt].PB(x), T2[cnt].PB(y);
p2[cnt] = jump2[cnt] = cnt;
time2[cnt] = i;
cnt++;
}
}
rt2 = cnt - 1;
for(int i = 0; i < cnt; i++)
st2[i][0] = p2[i];
for(int j = 1; j < 20; j++)
for(int i = 0; i < cnt; i++)
st2[i][j] = st2[st2[i][j - 1]][j - 1];
}
vi order1;
{
function<void(int)> dfs = [&] (int u) {
l1[u] = SZ(order1);
if(T1[u].empty()) {
assert(0 <= u && u < n);
order1.PB(u);
}
for(int v:T1[u])
dfs(v);
r1[u] = SZ(order1);
};
dfs(rt1);
}
vi pos(n);
for(int i = 0; i < n; i++)
pos[order[i]] = i;
vi order2;
{
function<void(int)> dfs = [&] (int u) {
l2[u] = SZ(order2);
if(T2[u].empty()) {
assert(0 <= u && u < n);
order2.PB(pos[u]);
}
for(int v:T2[u])
dfs(v);
r2[u] = SZ(order2);
};
dfs(rt2);
}
vi ans(q);
for(int i = 0; i < q; i++) {
int e = E[i], s = S[i], l = L[i], r = R[i];
for(int j = 19; j >= 0; j--) {
if(time1[st1[e][j]] <= r) {
e = st1[e][j];
}
}
for(int j = 19; j >= 0; j--) {
if(time2[st2[s][j]] >= l) {
s = st2[s][j];
}
}
int lb = l1[e], rb = r1[e];
for(int j = l2[s]; j < r2[s]; j++) {
if(lb <= order2[j] && order2[j] < rb) {
ans[i] = 1;
break;
}
}
// [l1[e], r1[e]) of order1
// [l2[s], r2[s]) of order2
}
return ans;
}
Compilation message
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:103:13: error: 'order' was not declared in this scope; did you mean 'order1'?
103 | pos[order[i]] = i;
| ^~~~~
| order1
