#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200000;
vector<int> adj[N];
vector<int> s;
vector<int> e;
vector<int> l;
vector<int> r;
vector<int> x;
vector<int> y;
int n;
int q;
vector<int> line;
int bit[N][20][2];
int bit2[N][20][2];
vector<int> vis[2];
void dfs(int node, int q1, int typ)
{
if (typ == 0 && node < l[q1]) return;
if (typ == 1 && node > r[q1]) return;
vis[typ][node] = true;
for (int next : adj[node])
{
if (vis[typ][next]) continue;
dfs(next, q1, typ);
}
}
void cons1()
{
for (int i = 0; i < n; i++)
{
bit[i][0][0] = line[i];
bit[i][0][1] = line[i];
}
for (int j = 1; j < 20; j++)
{
for (int i = 0; i + (1 << j) - 1 < n; i++)
{
bit[i][j][0] = min(bit[i][j - 1][0], bit[i + (1 << (j - 1))][j - 1][0]);
bit[i][j][1] = max(bit[i][j - 1][1], bit[i + (1 << (j - 1))][j - 1][1]);
}
}
}
void cons2()
{
for (int i = 0; i < n; i++)
{
bit2[i][0][0] = line[i];
bit2[i][0][1] = line[i];
}
for (int j = 1; j < 20; j++)
{
for (int i = n - 1; i - (1 << j) + 1 >= 0; i--)
{
bit2[i][j][0] = min(bit2[i][j - 1][0], bit2[i - (1 << (j - 1))][j - 1][0]);
bit2[i][j][1] = max(bit2[i][j - 1][1], bit2[i - (1 << (j - 1))][j - 1][1]);
}
}
}
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;
x =X;
y =Y;
s =S;
e =E;
l = L;
r =R;
for (int i = 0; i < x.size(); i++)
{
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
q = S.size();
std::vector<int> res(q);
if (n <= 3000 && q <= 3000)
{
if (s[q1] < l[q1])
{
res[q1] = 0;
continue;
}
if (e[q1] > r[q1])
{
res[q1] = 0;
continue;
}
for (int q1 = 0; q1 < q; q1++)
{
vis[0].clear();
vis[0].resize(n);
vis[1].clear();
vis[1].resize(n);
dfs(s[q1], q1, 0);
dfs(e[q1], q1, 1);
for (int i = 0; i < n; i++) if (vis[0][i] && vis[1][i]) res[q1] = 1;
}
} else
{
for (int i = 0; i < n; i++)
{
if (adj[i].size() == 1)
{
line.push_back(i);
break;
}
}
int prev = -1;
while (true)
{
int cnext = - 1;
for (int next : adj[line.back()])
{
if (next != prev)
{
cnext = next;
}
}
prev = line.back();
if (cnext == -1) break;
line.push_back(cnext);
}
vector<int> isAt(n);
for (int i = 0; i < n; i++) isAt[line[i]] = i;
cons1();
cons2();
for (int q1 = 0; q1 < q; q1++)
{
if (s[q1] < l[q1])
{
res[q1] = 0;
continue;
}
if (e[q1] > r[q1])
{
res[q1] = 0;
continue;
}
int a = isAt[s[q1]];
int b = isAt[e[q1]];
if (a < b)
{
for (int i = 19; i >= 0; i--)
{
if (a + ((1 << i)) < n && bit[a][i][0] >= l[q1])
{
a += (1 << i);
}
}
for (int i = 19; i >= 0; i--)
{
if (b - ((1 << i)) >= 0 && bit2[b][i][1] <= r[q1])
{
b -= ((1 << i));
}
}
if (a >= b) res[q1] = 1;
} else
{
swap(a, b);
for (int i = 19; i >= 0; i--)
{
if (a + ((1 << i)) < n && bit[a][i][1] <= r[q1])
{
a += (1 << i);
}
}
for (int i = 19; i >= 0; i--)
{
if (b - ((1 << i)) >= 0 && bit2[b][i][0] >= l[q1])
{
b -= ((1 << i));
}
}
if (a > b) res[q1] = 1;
}
}
}
return res;
}
/*
10 9 1
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
1 7 1 8
2
*/
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:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i = 0; i < x.size(); i++)
| ~~^~~~~~~~~~
werewolf.cpp:95:11: error: 'q1' was not declared in this scope; did you mean 'q'?
95 | if (s[q1] < l[q1])
| ^~
| q
werewolf.cpp:98:9: error: continue statement not within a loop
98 | continue;
| ^~~~~~~~
werewolf.cpp:100:11: error: 'q1' was not declared in this scope; did you mean 'q'?
100 | if (e[q1] > r[q1])
| ^~
| q
werewolf.cpp:103:9: error: continue statement not within a loop
103 | continue;
| ^~~~~~~~
