#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define vi vector<int>
#define pii pair<int, int>
const int MX = 2e5 + 5;
vector<int> gr[4][MX];
int vis[MX];
int n, m, q;
vi X, Y, S, E, L, R;
struct KRT{
int n;
vector<int> p;
KRT(int N){
this->n = N;
p.assign(N + 5, 0);
for(int i=1; i<=n; ++i){
p[i] = i;
}
}
int get(int u){
return (u == p[u] ? u : p[u] = get(p[u]));
}
void add(int u, int v, int k){
u = get(u), v = get(v);
if(u == v){
return;
}
p[v] = u;
gr[k][u].push_back(v);
}
};
struct BIT{
int n;
vector<int> f;
BIT(int N){
this->n = N + 5;
f.assign(N + 5, 0);
}
void update(int i, int val){
while(i < n){
f[i] += val;
i += (i & -i);
}
}
int get(int i){
int ans = 0;
while(i > 0){
ans += f[i];
i -= (i & -i);
}
return ans;
}
int get(int l, int r){
return get(r) - get(l - 1);
}
};
struct query{
int l, r, e, s, idx;
};
int in[4][MX], ou[4][MX];
int eu[4][MX];
int id = 0;
void dfs(int u, int p, int k){
eu[k][++id] = u;
in[k][u] = id;
for(int v : gr[k][u]){
if(v != p){
dfs(v, u, k);
eu[k][++id] = u;
ou[k][u] = id;
}
}
}
vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R){ //returns boolean vector.
for(int i=0; i<m; ++i){
int u = X[i], v = Y[i];
gr[1][u].push_back(v);
gr[1][v].push_back(u);
}
KRT up(n), dn(n);
for(int i=1; i<=n; ++i){
for(int u : gr[1][i]){
if(vis[u] == 1){
up.add(i, u, 2);
}
}
vis[i] = 1;
}
for(int i=n; i>=1; --i){
for(int u : gr[1][i]){
if(vis[u] == 2){
dn.add(i, u, 3);
}
}
vis[i] = 2;
}
for(int i=1; i<=n; ++i){
if(up.get(i) == i){
dfs(i, 0, 2);
break;
}
}
id = 0;
for(int i=1; i<=n; ++i){
if(dn.get(i) == i){
dfs(i, 0, 3);
break;
}
}
vector<query> Q;
vector<int> ans;
for(int i=0; i<q; ++i){
int s = S[i], e = E[i], l = L[i], r = R[i];
// Q.push_back({l, r, s, e, i});
set<int> se;
for(int j=in[3][l]+1; j<ou[3][l]; ++j){
// cout<<eu[3][j]<<' ';
se.insert(eu[3][j]);
}
// cout<<" -- ";
int f = 0;
for(int j=in[2][r]+1; j<ou[2][r]; ++j){
if(se.find(eu[2][j]) != se.end()){
f = 1;
// break;
}
// cout<<eu[2][j]<<' ';
}
// cout<<endl;
ans.push_back(f);
}
// sort(Q.begin(), Q.end(), [](query u, query v){
// return (u.l < v.l);
// });
return ans;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("main.inp","r",stdin);
// freopen("main.out","w",stdout);
cin>>n>>m>>q;
for(int i=1; i<=m; ++i){
int u, v;
cin>>u>>v;
++u, ++v;
X.push_back(u);
Y.push_back(v);
}
for(int i=1; i<=q; ++i){
int s, e, l, r;
cin>>s>>e>>l>>r;
++s, ++e, ++l, ++r;
S.push_back(s), E.push_back(e), L.push_back(l), R.push_back(r);
}
vector<int> ans = check_validity(n, X, Y, S, E, L, R);
for(int x : ans){
cout<<x<<' ';
}
return 0;
}
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:128:13: warning: unused variable 's' [-Wunused-variable]
128 | int s = S[i], e = E[i], l = L[i], r = R[i];
| ^
werewolf.cpp:128:23: warning: unused variable 'e' [-Wunused-variable]
128 | int s = S[i], e = E[i], l = L[i], r = R[i];
| ^
/usr/bin/ld: /tmp/ccOq5PKO.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccuJYwEM.o:werewolf.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
