//#include "werewolf.h"
#include <bits/stdc++.h>
#define maxn 200010
#define loop(i, a, b) for(int i=a;i<b;i++)
#define cc(a) cout<< a << endl;
using namespace std;
struct seg{
map<int, map<int, bool>> tree;
void update(int x, int y){
x+=maxn;y+=maxn;
tree[x][y]=1;
for(int tx=x;tx>=1;tx>>=1){
for(int ty=y;ty>=1;ty>>=1) tree[tx][ty]=1;
}
}
bool query(int lx, int ly, int rx, int ry){
bool ret=0;
lx+=maxn;ly+=maxn;rx+=maxn;ry+=maxn;
int slx=lx; int srx=rx;
for(;slx<srx;slx>>=1, srx>>=1){
if(slx&1){
int sly=ly; int sry=ry;
for(;sly<sry;sly>>=1, sry>>=1){
if(sly&1) ret=ret or tree[slx][sly++];
if(sry&1) ret=ret or tree[slx][--sry];
}
slx++;
}
if(srx&1){
--srx;
int sly=ly; int sry=ry;
for(;sly<sry;sly>>=1, sry>>=1){
if(sly&1) ret=ret or tree[srx][sly++];
if(sry&1) ret=ret or tree[srx][--sry];
}
}
}
return ret;
}
};
vector<int> edges[maxn];
int pU[maxn];int pV[maxn];
vector<int> cU[maxn];vector<int> cV[maxn];
int fndU(int u){return (u==pU[u]) ? u:fndU(pU[u]);}
int fndV(int u){return (u==pV[u]) ? u:fndV(pV[u]);}
int eulU[maxn * 2];int eulV[maxn * 2];
int sU[maxn];int eU[maxn];int sV[maxn];int eV[maxn];
int cntU=0;int cntV=0;
void dfsU(int u){
sU[u]=cntU;eulU[cntU++]=u;
for(auto&& v:cU[u]) dfsU(v);
eU[u]=cntU;eulU[cntU++]=u;
}
void dfsV(int u){
sV[u]=cntV;eulV[cntV++]=u;
for(auto&& v:cV[u]) dfsV(v);
eV[u]=cntV;eulV[cntV++]=u;
}
seg r;
int faU(int u, int m){
if (u==pU[u] or pU[u]>m) return u;
return faU(pU[u], m);
}
int faV(int u, int m){
if (u==pV[u] or pV[u]<m) return u;
return faV(pV[u], m);
}
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) {
int M=X.size();int Q=S.size();
loop(i, 0, M){edges[X[i]].push_back(Y[i]);edges[Y[i]].push_back(X[i]);}
loop(i, 0, N) pU[i]=i;loop(i, 0, N) pV[i]=i;
loop(i, 0, N){
for(auto&& j: edges[i]){
if(j>i) continue;
int pj=fndU(j);
if(pj==i) continue;
pU[pj]=i;cU[i].push_back(pj);
}
}//disjoint union U
for(int i=N-1;i>=0;i--){
for(auto&& j: edges[i]){
if(j<i) continue;
int pj=fndV(j);
if(pj==i) continue;
pV[pj]=i;cV[i].push_back(pj);
}
}//disjoint union V
dfsU(N-1);dfsV(0);
loop(i, 0, N) r.update(sU[i], sV[i]);
vector<int> ans;ans.resize(Q);
loop(i, 0, Q){
int na=faV(S[i], L[i]);int nb=faU(E[i], R[i]);
ans[i]=r.query(sU[nb], sV[na], eU[nb], eV[na]);
//cout << na << " "<< nb << endl;
cc(ans[i]);
}
return ans;
}
int main() {
int n, m, q, a, b;cin >> n >>m >>q;
vector<int> x, y;
loop(i, 0, m){
scanf("%d%d", &a, &b);
x.push_back(a);y.push_back(b);
}
vector<int> s, e, l, r;int ts, te, tl, tr;
loop(i, 0, q){
scanf("%d%d%d%d", &ts, &te,&tl, &tr);
s.push_back(ts);e.push_back(te);l.push_back(tl);r.push_back(tr);
}
check_validity(n, x, y, s, e, l, r);
}
Compilation message
werewolf.cpp: In function 'int main()':
werewolf.cpp:134:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
werewolf.cpp:139:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &ts, &te,&tl, &tr);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/cctB75Hp.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccurzSqy.o:werewolf.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
