#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
#define LL long long
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define f first
#define s second
vector<vector<int>> adj;
struct DSU {
vector<int> par, size, top;
bool topmax;
DSU(int N, bool mx){
par.resize(N); size.resize(N); top.resize(N);
for (int i = 0; i < N; ++i) {
size[i] = 1;
par[i] = i;
top[i] = i;
}
topmax = mx;
}
int find(int node) {
if (par[node] != node) {
par[node] = find(par[node]);
}
return par[node];
}
void merge(int A, int B) {
int rootA = find(A);
int rootB = find(B);
if (rootA == rootB) return;
top[rootA] = top[rootB] = topmax ? max(top[rootA], top[rootB]) : min(top[rootA], top[rootB]);
if (size[rootA] > size[rootB]) {
par[rootB] = rootA;
size[rootA] += size[rootB];
}
else {
par[rootA] = rootB;
size[rootB] += size[rootA];
}
}
};
struct MST {
vector<vector<int>> tree;
vector<int> lBound, rBound;
MST(vector<int> &input) {
tree.resize(4*input.size()+1);
lBound.resize(4*input.size()+1);
rBound.resize(4*input.size()+1);
build(0, 0, input.size()-1, input);
}
void build(int node, int L, int R, vector<int> &arr) {
lBound[node] = L; rBound[node] = R;
if (L == R) {
tree[node].pb(arr[L]); return;
}
build(2*node+1, L, (L+R)/2, arr); build(2*node+2, (L+R)/2+1, R, arr);
auto lptr = tree[2*node+1].begin(), rptr = tree[2*node+2].begin();
auto lend = tree[2*node+1].end(), rend = tree[2*node+2].end();
while(lptr != lend && rptr != rend) {
if (*lptr < *rptr) {
tree[node].pb(*lptr);
lptr++;
} else {
tree[node].pb(*rptr);
rptr++;
}
}
while(lptr != lend) {
tree[node].pb(*lptr);
lptr++;
}
while(rptr != rend) {
tree[node].pb(*rptr);
rptr++;
}
}
bool contains(int node, int dL, int dR) {
if (tree[node].back() < dL || tree[node].front() > dR) return false;
int min = -1, max = tree[node].size()-1;
while(max-min > 1) {
int mid = (min+max) >> 1;
if (tree[node][mid] >= dL) {
max = mid;
} else {
min = mid;
}
}
if (tree[node][max] <= dR) return true;
return false;
}
bool query(int node, int qL, int qR, int dL, int dR) {
if (qR < lBound[node] || qL > rBound[node]) return false;
if (qL <= lBound[node] && rBound[node] <= qR) {
return contains(node, dL, dR);
}
return query(2*node+1, qL, qR, dL, dR) || query(2*node+2, qL, qR, dL, dR);
}
};
vector<int> hstart, hend, wstart, wend;
int hpar[19][200005], wpar[19][200005];
vector<int> input;
void hdfs(int c, int p, vector<int> &heuler, vector<vector<int>> &hadj) {
hpar[0][c] = p;
hstart[c] = heuler.size();
heuler.pb(c);
for (int to : hadj[c]) {
hdfs(to, c, heuler, hadj);
}
hend[c] = heuler.size()-1;
}
int cwidx = 0;
void wdfs(int c, int p, vector<int> &widx, vector<vector<int>> &wadj) {
wpar[0][c] = p;
widx[c] = cwidx;
wstart[c] = cwidx;
cwidx++;
for (int to : wadj[c]) {
wdfs(to, c, widx, wadj);
}
wend[c] = cwidx-1;
}
void input_gen(int N, vector<int> &X, vector<int> &Y, vector<int> &S, vector<int> &E, vector<int> &L, vector<int> &R) {
vector<int> heuler, widx;
vector<vector<int>> hadj, wadj;
adj.resize(N+5);
for (int i = 0; i < X.size(); i++) {
adj[X[i]].pb(Y[i]); adj[Y[i]].pb(X[i]);
}
hadj.resize(N+5); wadj.resize(N+5);
widx.resize(N+5);
DSU h(N+5, false), w(N+5, true);
for (int i = N-1; i >= 0; i--) {
unordered_set<int> added;
for (int to : adj[i]) {
if (to > i) {
int root = h.find(to);
int rtop = h.top[root];
if (added.find(rtop) == added.end()) {
added.insert(rtop);
hadj[i].pb(rtop);
}
}
}
for (int val : added) h.merge(i, val);
}
for (int i = 0; i < N; i++) {
unordered_set<int> added;
for (int to : adj[i]) {
if (to < i) {
int root = w.find(to);
int rtop = w.top[root];
if (added.find(rtop) == added.end()) {
added.insert(rtop);
wadj[i].pb(rtop);
}
}
}
for (int val : added) w.merge(i, val);
}
hdfs(0, -1, heuler, hadj); wdfs(N-1, -1, widx, wadj);
input.resize(N);
for (int i = 0; i < N; i++) {
input[i] = widx[heuler[i]];
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
ios::sync_with_stdio(0);
hstart.resize(N+5); hend.resize(N+5);
wstart.resize(N+5); wend.resize(N+5);
input_gen(N, X, Y, S, E, L, R);
MST tree(input);
for (int i = 1; i <= 18; i++) {
for (int j = 0; j < N; j++) {
if (hpar[i-1][j] == -1) hpar[i][j] = -1;
else hpar[i][j] = hpar[i-1][hpar[i-1][j]];
if (wpar[i-1][j] == -1) wpar[i][j] = -1;
else wpar[i][j] = wpar[i-1][wpar[i-1][j]];
}
}
vector<int> ret;
for (int q = 0; q < S.size(); q++) {
if (S[q] < L[q] || E[q] > R[q]) {
cout << 0 << endl; continue;
}
for (int i = 18; i >= 0; i--) {
if (hpar[i][S[q]] >= L[q]) {
S[q] = hpar[i][S[q]];
}
if (wpar[i][E[q]] != -1 && wpar[i][E[q]] <= R[q]) {
E[q] = wpar[i][E[q]];
}
}
ret.pb(tree.query(0, hstart[S[q]], hend[S[q]], wstart[E[q]], wend[E[q]]));
}
return ret;
}
int main() {
int N, M, Q;
cin >> N >> M >> Q;
vector<int> X, Y, S, E, L, R;
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
X.pb(a); Y.pb(b);
}
for (int i = 0; i < Q; i++) {
int s, e, l, r;
cin >> s >> e >> l >> r;
S.pb(s); E.pb(e); L.pb(l); R.pb(r);
}
vector<int> ret = check_validity(N, X, Y, S, E, L, R);
for (int i = 0; i < ret.size(); i++) {
cout << ret[i] << endl;
}
}
Compilation message
werewolf.cpp: In function 'void input_gen(int, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
werewolf.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for (int i = 0; i < X.size(); i++) {
| ~~^~~~~~~~~~
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:201:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | for (int q = 0; q < S.size(); q++) {
| ~~^~~~~~~~~~
werewolf.cpp: In function 'int main()':
werewolf.cpp:233:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
233 | for (int i = 0; i < ret.size(); i++) {
| ~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccW0TWVa.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccRcv7qa.o:werewolf.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
