/*
Works, but to slow because of need for specific merge in the union find, which can be exploited
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#ifdef EVAL
#include "werewolf.h"
#else
#include "grader.cpp"
#endif
struct Query {
ll start, end;
ll low, high;
ll index;
Query(ll start, ll end, ll low, ll high, ll index) : start(start), end(end), low(low), high(high), index(index) {}
};
const ll LEN = 200005;
array<vector<ll>, LEN> adj;
array<vector<ll>, LEN> new_adj;
vector<Query> queries;
array<ll, LEN> sz;
array<pair<ll, ll>, LEN> parent;
array<vector<ll>, LEN> children;
array<pair<ll, ll>, LEN> range;
array<ll, LEN> translator;
array<ll, LEN> back_translator;
array<ll, LEN> new_parent;
array<set<ll>, LEN> new_nodes;
void insert(ll i) {
parent[i] = {i, -1};
sz[i] = 1;
}
void insert_new(ll i) {
new_parent[i] = i;
new_nodes[i].insert(i);
}
ll get_parent_new(ll i) {
if (new_parent[i] == i) return i;
return new_parent[i] = get_parent_new(new_parent[i]);
}
void merge_new(ll a, ll b) {
if (new_parent[a] == -1 || new_parent[b] == -1) return;
a = get_parent_new(a);
b = get_parent_new(b);
if (new_nodes[b].size() > new_nodes[a].size()) swap(a, b);
new_parent[b] = a;
new_nodes[a].merge(new_nodes[b]);
}
ll get_parent(ll i, ll threshold = 1e18) {
if (parent[i].first == i || parent[i].second > threshold) return i;
return get_parent(parent[i].first, threshold);
}
void merge_sets(ll a, ll b, ll threshold) {
if (parent[a].first == -1 || parent[b].first == -1) return;
a = get_parent(a);
b = get_parent(b);
if (a == b) return;
if (a < b) swap(a, b);
parent[b] = {a, threshold};
children[a].push_back(b);
sz[a] += sz[b];
}
ll from_pos(ll i, ll index) {
index++;
translator[i] = index;
back_translator[index] = i;
range[index].first = index;
for (auto c: children[i]) {
index = from_pos(c, index);
}
range[translator[i]].second = index;
return index;
}
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)
{
ll n = N;
for (int i = 0; i < X.size(); i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int i = 0; i < S.size(); i++) {
queries.push_back(Query(S[i], E[i], L[i], R[i], i));
}
parent.fill({-1, -1});
for (int i = 0; i < n; i++) {
insert(i);
for (auto a: adj[i]) {
merge_sets(i, a, i);
}
}
from_pos(get_parent(0), -1);
new_parent.fill(-1);
for (int i = 0; i < n; i++) {
for (auto a: adj[i]) {
new_adj[translator[i]].push_back(translator[a]);
}
}
sort(queries.begin(), queries.end(), [](Query &a, Query &b) {
return a.low < b.low;
});
vector<int> sol(queries.size(), 0);
// loop from top over all queries
Query query = {0, 0, 0, 0, 0};
pair<ll, ll> rg;
ll c1, c2, c3;
for (int i = n - 1; i >= 0; i--) {
insert_new(translator[i]);
for (auto a: new_adj[translator[i]]) {
merge_new(translator[i], a);
}
/*
Human(high pop. areas) -> Werewolf(low pop. areas)
*/
while (queries.size() && queries.back().low == i) {
query = queries.back(); queries.pop_back();
// set of new nodes for when still a human (so only high populated areas)
c1 = get_parent_new(translator[query.start]);
// new nodes set
set<ll> &nodes = new_nodes[c1];
// range for while a werewolf (so only low populated areas)
c1 = get_parent(query.end, query.high);
// new nodes range
rg = range[translator[c1]];
auto it = nodes.lower_bound(rg.first);
if (it == nodes.end()) continue;
else if (*it <= rg.second) sol[query.index] = 1;
}
}
return sol;
}
/*
6 6 3
0 3
3 4
3 1
1 2
2 5
5 1
4 2 1 2
4 2 2 2
5 4 3 4
*/
