#include <vector>
#include <algorithm>
#include <memory.h>
#include <iostream>
#include "werewolf.h"
#include "grader.cpp"
#define pb push_back
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define okk puts("OK");
using namespace std;
const int smallN = (int)6e3 + 7;
const int N = (int)2e5 + 7;
int was[smallN];
int used[smallN];
vector < int > gr[N];
int l, r;
int n;
void dfs1(int v, int pr) {
was[v]++;
used[v] = 1;
for (int to : gr[v]) {
if (!used[to] && to >= l) dfs1(to, v);
}
}
void dfs2(int v, int pr) {
was[v]++;
used[v] = 1;
for (int to : gr[v]) {
if (!used[to] && to <= r) dfs2(to, v);
}
}
vector < int > subtask12(int &N, vector < int > &X, vector < int > &Y, vector < int > &S, vector < int > &E, vector < int > &L, vector < int > &R) {
n = N;
for (int i = 0; i < (int)X.size(); i++) {
gr[X[i]].pb(Y[i]);
gr[Y[i]].pb(X[i]);
}
vector < int > ans;
int q = S.size();
for (int i = 0; i < q; i++) {
l = L[i];
r = R[i];
memset(was, 0, sizeof was);
dfs1(S[i], S[i]);
memset(used, 0, sizeof used);
dfs2(E[i], E[i]);
memset(used, 0, sizeof used);
int ok = 1;
for (int j = l; j <= r; j++) {
if (was[j] == 2) {
ans.pb(1);
ok = 0;
break;
}
}
if (ok) {
ans.pb(0);
}
}
return ans;
}
struct sparse {
int table[2][20][N];
/*
0 = min
1 = max
*/
sparse() {
}
int numlog[N];
void build(vector < int > &a) {
numlog[0] = numlog[1] = 0;
int nn = a.size();
for (int i = 2; i < N; i++) {
numlog[i] = numlog[i / 2] + 1;
}
for (int i = 0; i < 20; i++) {
for (int j = 0; j < nn; j++) {
if (i == 0) {
table[0][i][j] = table[1][i][j] = a[j];
} else {
table[0][i][j] = min(table[0][i - 1][j], table[0][i - 1][min(j + (1 << (i - 1)), nn - 1)]);
table[1][i][j] = max(table[1][i - 1][j], table[1][i - 1][min(j + (1 << (i - 1)), nn - 1)]);
}
}
}
}
int getmax(int l, int r) {
int lg = numlog[r - l + 1];
return max(table[1][lg][l], table[1][lg][r - (1 << lg) + 1]);
}
int getmin(int l, int r) {
int lg = numlog[r - l + 1];
return min(table[0][lg][l], table[0][lg][r - (1 << lg) + 1]);
}
};
vector < int > ar;
vector < int > pos;
sparse tb;
void dfs3(int v, int pr, int h = 0) {
ar[h] = v;
for (int to : gr[v]) {
if (to != pr) {
dfs3(to, v, h + 1);
}
}
}
pii getrange1(int v, int lim) {
pii ret;
ret = mk(v, v);
int lo, hi;
lo = 1;
hi = n + 1;
while (hi - lo > 1) {
int md = (lo + hi) >> 1;
if (tb.getmin(max(0, v - md + 1), v) >= lim) {
lo = md;
} else {
hi = md;
}
}
ret.fr = max(0, v - lo + 1);
lo = 1;
hi = n + 1;
while (hi - lo > 1) {
int md = (lo + hi) >> 1;
if (tb.getmin(v, min(v + md - 1, n - 1)) >= lim) {
lo = md;
} else {
hi = md;
}
}
ret.sc = min(v + lo - 1, n - 1);
return ret;
}
pii getrange2(int v, int lim) {
pii ret;
ret = mk(v, v);
int lo, hi;
lo = 1;
hi = n + 1;
while (hi - lo > 1) {
int md = (lo + hi) >> 1;
if (tb.getmax(max(0, v - md + 1), v) <= lim) {
lo = md;
} else {
hi = md;
}
}
ret.fr = max(0, v - lo + 1);
lo = 1;
hi = n + 1;
while (hi - lo > 1) {
int md = (lo + hi) >> 1;
if (tb.getmax(v, min(v + md - 1, n - 1)) <= lim) {
lo = md;
} else {
hi = md;
}
}
ret.sc = min(v + lo - 1, n - 1);
return ret;
}
vector < int > subtask3(int &N, vector < int > &X, vector < int > &Y, vector < int > &S, vector < int > &E, vector < int > &L, vector < int > &R) {
n = N;
int m = X.size();
ar.resize(n);
pos.resize(n);
vector < int > ans;
for (int i = 0; i < m; i++) {
gr[X[i]].pb(Y[i]);
gr[Y[i]].pb(X[i]);
}
for (int i = 0; i < n; i++) {
if ((int)gr[i].size() == 1) {
dfs3(i, i);
break;
}
}
tb.build(ar);
for (int i = 0; i < n; i++) {
pos[ar[i]] = i;
}
int q = (int)S.size();
ans.resize(q);
for (int i = 0; i < q; i++) {
int &res = ans[i];
res = 0;
pair < int, int > asd1 = getrange1(pos[S[i]], L[i]);
pair < int, int > asd2 = getrange2(pos[E[i]], R[i]);
if ((pos[S[i]] <= pos[E[i]] && asd1.sc >= asd2.fr) || (pos[E[i]] <= pos[S[i]] && asd2.sc >= asd1.fr)) {
res = 1;
}
}
return ans;
}
struct DSU {
int par[N];
DSU() {
iota(par, par + N, 0);
}
int getpar(int x) {
return ((par[x] == x) ? x : getpar(par[x]));
}
};
DSU dsu1, dsu2;
struct query {
int id, t, x;
query() {
}
query(int _id, int _t, int _x) {
id = _id;
t = _t;
x = _x;
}
};
vector < query > qq;
struct fen {
int tree[N];
fen() {
memset(tree, 0, sizeof tree);
}
void upd(int pos) {
while (pos < N) {
tree[pos]++;
pos = pos | (pos + 1);
}
}
int get(int r) {
int res = 0;
while (r >= 0) {
res += tree[r];
r = (r & (r + 1)) - 1;
}
return res;
}
};
fen tr;
vector < vector < int > > gr1, gr2;
int par[2][20][N];
int tiktak;
int tin[2][N], tout[2][N];
int pos1[N];
void dfs(vector < vector < int > > &GR, int id, int v, int pr) {
par[id][0][v] = pr;
for (int i = 1; i < 20; i++) {
par[id][i][v] = par[id][i - 1][par[id][i - 1][v]];
}
tin[id][v] = ++tiktak;
for (int to : GR[v]) {
dfs(GR, id, to, v);
}
tout[id][v] = tiktak;
}
vector < int > subtask4(int &N, vector < int > &X, vector < int > &Y, vector < int > &S, vector < int > &E, vector < int > &L, vector < int > &R) {
n = N;
dsu1 = DSU();
dsu2 = DSU();
int m = X.size();
int q = S.size();
vector < int > ans;
gr1.resize(n);
gr2.resize(n);
ans.resize(q);
for (int i = 0; i < m; i++) {
gr[X[i]].pb(Y[i]);
gr[Y[i]].pb(X[i]);
}
for (int i = n - 1; i >= 0; i--) {
for (int to : gr[i]) {
if (i > to) continue;
int x = dsu1.getpar(i);
int y = dsu1.getpar(to);
if (x == y) continue;
dsu1.par[y] = x;
gr1[x].pb(y);
}
}
for (int i = 0; i < n; i++) {
for (int to : gr[i]) {
if (i < to) continue;
int x = dsu2.getpar(i);
int y = dsu2.getpar(to);
if (x == y) continue;
dsu2.par[y] = x;
gr2[x].pb(y);
}
}
dfs(gr1, 0, dsu1.getpar(0), dsu1.getpar(0));
tiktak = 0;
dfs(gr2, 1, dsu2.getpar(0), dsu2.getpar(0));
for (int i = 0; i < q; i++) {
int x = S[i];
int y = E[i];
int l = L[i];
int r = R[i];
for (int j = 19; j >= 0; j--) {
if (par[0][j][x] >= l) x = par[0][j][x];
if (par[1][j][y] <= r) y = par[1][j][y];
}
// cout << i << ' ' << x << ' ' << y << endl;
qq.pb(query(~i, tin[0][x] - 1, y));
qq.pb(query(i, tout[0][x], y));
}
sort(qq.begin(), qq.end(), [&](query &a, query &b) {
return a.t < b.t;
});
// puts("***");
for (int i = 0; i < n; i++) {
pos1[tin[0][i] - 1] = tin[1][i];
}
int ord = 0;
q = (int)qq.size();
/*for (auto to : qq) {
cout << to.id << ' ' << to.t << ' ' << to.x << '\n';
} */
for (int i = 0; i < q; i++) {
while (ord < qq[i].t) tr.upd(pos1[ord++]);
int delta = tr.get(tout[1][qq[i].x]) - tr.get(tin[1][qq[i].x] - 1);
if (qq[i].id < 0) {
ans[~qq[i].id] -= delta;
} else {
ans[qq[i].id] += delta;
}
}
for (int i = 0; i < q; i++) {
ans[i] = (ans[i] > 0);
}
return ans;
}
vector < int > check_validity(int N, vector < int > X, vector < int > Y, vector < int > S, vector < int > E, vector < int > L, vector < int > R) {
return subtask4(N, X, Y, S, E, L, R);
if (N <= 3000 && (int)X.size() <= 6000 && (int)S.size() <= 3000) {
return subtask12(N, X, Y, S, E, L, R);
} else if ((int)X.size() == N - 1) {
return subtask3(N, X, Y, S, E, L, R);
}
return subtask4(N, X, Y, S, E, L, R);
}
Compilation message
werewolf.cpp: In constructor 'DSU::DSU()':
werewolf.cpp:217:3: error: 'iota' was not declared in this scope
iota(par, par + N, 0);
^~~~
werewolf.cpp:217:3: note: suggested alternative: 'int'
iota(par, par + N, 0);
^~~~
int
