#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 3000 + 7;
int n, m, col;
vector<int> le, ri;
int act[N];
vector<int> adj[N];
vector<int> QL[N], QR[N];
int ST[N], EN[N];
int ro1[N], ro2[N];
struct tree
{
vector<int> adj[N];
int st[N], en[N], vec[N], t;
tree() {}
void dfs(int x, int p)
{
st[x] = ++t;
if (x < n)
vec[t] = x;
else
vec[t] = -1;
for (auto u : adj[x])
{
if (u == p)
continue;
dfs(u, x);
}
en[x] = ++t;
vec[t] = -1;
}
vector<int> inter(int x)
{
vector<int> ret;
for (int i = st[x]; i <= en[x]; ++i)
{
if (~vec[i])
{
ret.push_back(vec[i]);
}
}
return ret;
}
} t1, t2;
struct dsu
{
int fat[N];
dsu() { iota(fat, fat + N, 0); }
int find(int x) { return fat[x] = x == fat[x] ? x : find(fat[x]); }
void link(int u, int v)
{
u = find(u), v = find(v);
if (u > v)
swap(u, v);
fat[u] = v;
}
inline bool same(int u, int v) { return find(u) == find(v); }
} d;
void build(tree &t, int dir)
{
dsu d;
int lst = n;
++col;
for (int i = (dir == 1 ? 0 : n - 1); i >= 0 && i < n; i += dir)
{
for (auto u : adj[i])
{
if (act[u] == col)
{
int x = d.find(u);
t.adj[lst].push_back(x);
if (!d.same(lst, x))
{
d.link(x, lst);
}
}
}
t.adj[lst].push_back(i);
d.link(i, lst);
++lst;
if (dir == -1)
{
for (auto u : QL[i])
{
ro1[u] = d.find(ST[u]);
}
}
else
{
for (auto u : QR[i])
{
ro2[u] = d.find(EN[u]);
}
}
act[i] = col;
}
}
std::vector<int> check_validity(int _N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R)
{
n = _N, m = X.size();
le = X, ri = Y;
int Q = S.size();
std::vector<int> A(Q);
for (int i = 0; i < m; ++i)
{
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int i = 0; i < Q; ++i)
{
QL[L[i]].push_back(i);
QR[R[i]].push_back(i);
ST[i] = S[i];
EN[i] = E[i];
}
build(t1, -1);
build(t2, 1);
t1.dfs(2 * n - 1, 2 * n - 1), t2.dfs(2 * n - 1, 2 * n - 1);
return A ;s
for (int i = 0; i < Q; ++i)
{
vector<int> v1 = t1.inter(ro1[i]);
vector<int> v2 = t2.inter(ro2[i]);
sort(v1.begin(), v1.end());
for (auto u : v2)
{
if (binary_search(v1.begin(), v1.end(), u))
{
A[i] = 1;
break;
}
}
}
return A;
}
Compilation message
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:129:18: error: 's' was not declared in this scope
129 | return A ;s
| ^
werewolf.cpp:130:24: error: 'i' was not declared in this scope
130 | for (int i = 0; i < Q; ++i)
| ^
