#include <bits/stdc++.h>
#include "wolf.h"
using namespace std;
const int LOG = 18;
struct unionfind{
vector<int> p;
unionfind(int N): p(N, -1){
}
int root(int x){
if (p[x] == -1){
return x;
} else {
p[x] = root(p[x]);
return p[x];
}
}
bool same(int x, int y){
return root(x) == root(y);
}
void unite(int x, int y){
x = root(x);
y = root(y);
if (x != y){
p[x] = y;
}
}
};
void dfs(vector<vector<int>> &c, vector<int> &L, vector<int> &R, int &t, int v){
L[v] = t;
t++;
for (int w : c[v]){
dfs(c, L, R, t, w);
}
R[v] = t;
}
struct binary_indexed_tree{
int N;
vector<int> BIT;
binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
}
void add(int i){
i++;
while (i <= N){
BIT[i]++;
i += i & -i;
}
}
int sum(int i){
int ans = 0;
while (i > 0){
ans += BIT[i];
i -= i & -i;
}
return ans;
}
int sum(int L, int R){
return sum(R) - sum(L);
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
int M = X.size();
int Q = S.size();
vector<vector<int>> G(N);
for (int i = 0; i < M; i++){
G[X[i]].push_back(Y[i]);
G[Y[i]].push_back(X[i]);
}
unionfind UF1(N);
vector<int> p1(N, -1);
vector<vector<int>> c1(N);
for (int i = N - 1; i >= 0; i--){
for (int j : G[i]){
if (j > i){
int x = UF1.root(i);
int y = UF1.root(j);
if (x != y){
p1[y] = x;
c1[x].push_back(y);
UF1.unite(y, x);
}
}
}
}
unionfind UF2(N);
vector<int> p2(N, -1);
vector<vector<int>> c2(N);
for (int i = 0; i < N; i++){
for (int j : G[i]){
if (j < i){
int x = UF2.root(i);
int y = UF2.root(j);
if (x != y){
p2[y] = x;
c2[x].push_back(y);
UF2.unite(y, x);
}
}
}
}
vector<int> L1(N), R1(N);
int t1 = 0;
dfs(c1, L1, R1, t1, 0);
vector<int> L2(N), R2(N);
int t2 = 0;
dfs(c2, L2, R2, t2, N - 1);
vector<vector<int>> pp1(LOG, vector<int>(N, -1));
pp1[0] = p1;
for (int i = 0; i < LOG - 1; i++){
for (int j = 0; j < N; j++){
if (pp1[i][j] != -1){
pp1[i + 1][j] = pp1[i][pp1[i][j]];
}
}
}
vector<vector<int>> pp2(LOG, vector<int>(N, -1));
pp2[0] = p2;
for (int i = 0; i < LOG - 1; i++){
for (int j = 0; j < N; j++){
if (pp2[i][j] != -1){
pp2[i + 1][j] = pp2[i][pp2[i][j]];
}
}
}
vector<int> X1(Q), X2(Q), Y1(Q), Y2(Q);
for (int i = 0; i < Q; i++){
int v1 = S[i];
for (int j = LOG - 1; j >= 0; j--){
if (pp1[j][v1] >= L[i]){
v1 = pp1[j][v1];
}
}
X1[i] = L1[v1];
X2[i] = R1[v1];
int v2 = E[i];
for (int j = LOG - 1; j >= 0; j--){
if (pp2[j][v1] != -1 && pp2[j][v1] <= R[i]){
v2 = pp2[j][v2];
}
}
Y1[i] = L2[v2];
Y2[i] = R2[v2];
}
vector<vector<int>> query_add(N + 1), query_sub(N + 1);
for (int i = 0; i < Q; i++){
query_sub[X1[i]].push_back(i);
query_add[X2[i]].push_back(i);
}
vector<vector<int>> upd(N + 1);
for (int i = 0; i < N; i++){
upd[L1[i]].push_back(L2[i]);
}
binary_indexed_tree BIT(N);
vector<int> ans(Q, 0);
for (int i = 0; i <= N; i++){
for (int j : query_add[i]){
ans[j] += BIT.sum(Y1[j], Y2[j]);
}
for (int j : query_sub[i]){
ans[j] -= BIT.sum(Y1[j], Y2[j]);
}
for (int j : upd[i]){
BIT.add(j);
}
}
for (int i = 0; i < Q; i++){
ans[i] = min(ans[i], 1);
}
return ans;
}
Compilation message
werewolf.cpp:2:10: fatal error: wolf.h: No such file or directory
2 | #include "wolf.h"
| ^~~~~~~~
compilation terminated.
