#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define maxn 400005
using namespace std;
ll m,n,p[maxn],in1[maxn],out1[maxn],in2[maxn],out2[maxn],ans[maxn];
ll tout1[maxn],tout2[maxn],tin1[maxn],tin2[maxn],s[maxn],t[maxn],l[maxn],r[maxn];
ll P1[200005][19],P2[200005][19],q,was[maxn],pown = 1;
vector<ll>v[maxn],ne[maxn],ol[maxn],be[maxn],ed[maxn];
vector<pair<ll,ll> >g;
ll tt[6000005];
ll timer = 0;
ll find(ll x){
if(p[x] == x)return x;
return p[x] = find(p[x]);
}
void join(ll x,ll y){
x = find(x);
y = find(y);
if(x == y)return;
if(y > x)swap(x,y);
p[y] = x;
}
void join1(ll x,ll y){
x = find(x);
y = find(y);
if(x == y)return;
if(y < x)swap(x , y);
p[y] = x;
}
void dfs(ll x, ll par){
timer++;
in1[x] = timer;
tin1[timer] = x;
P1[x][0] = par;
for(int i=1;i<=18;i++)
P1[x][i] = P1[P1[x][i-1]][i-1];
for(int i=0; i<ne[x].size(); i++)
if(ne[x][i] != par)
dfs(ne[x][i],x);
timer++;
out1[x] = timer;
tout1[timer] = x;
}
void dfs1(ll x,ll par){
timer++;
in2[x] = timer;
tin2[timer] = x;
P2[x][0] = par;
for(int i=1;i<=18;i++)
P2[x][i] = P2[P2[x][i-1]][i-1];
for(int i=0; i<ol[x].size(); i++)
if(ol[x][i] != par)
dfs1(ol[x][i],x);
timer++;
out2[x] = timer;
tout2[timer] = x;
}
ll bigne(ll x,ll y){
for(int i=18; i>=0; i--)
if(P1[x][i])
if(P1[x][i] <= y)
x = P1[x][i];
return x;
}
ll bigol(ll x,ll y){
for(int i=18; i>=0; i--)
if(P2[x][i])
if(P2[x][i] >= y)
x = P2[x][i];
return x;
}
void upd(ll x){
if(!x)return;
tt[x] = tt[2 * x] + tt[2 * x + 1];
upd(x / 2);
}
ll cnt(ll x,ll L,ll R,ll l1,ll r1){
if(L > r1 || R < l1)return 0;
if(L >= l1 && R <= r1)return tt[x];
ll k1 = cnt(2 * x,L , (L + R) / 2 , l1 , r1);
ll k2 = cnt(2 * x + 1,(L + R) / 2 + 1 , R , l1 , r1);
return k1 + k2;
}
int main(){
cin >> n >> m >> q;
while(pown <= 2 * n){
pown *= 2;
}
for(int i=1; i<=m; i++){
ll x,y;
cin >> x >> y;
x++;
y++;
v[x].pb(y);
v[y].pb(x);
g.pb(mp(max(x,y) , min(x,y)));
}
for(int i=1; i<=q; i++){
cin >> s[i] >> t[i] >> l[i] >> r[i];
s[i]++;
t[i]++;
l[i]++;
r[i]++;
}
sort(g.begin(),g.end());
for(int i=1; i<=n; i++){
p[i] = i;
}
for(int i=0; i<g.size(); i++){
ll x,y;
x = g[i].f;
y = g[i].s;
x = find(x);
y = find(y);
if(x != y){
join(x,y);
ne[x].pb(y);
ne[y].pb(x);
}
}
for(int i=0; i<g.size(); i++){
swap(g[i].f , g[i].s);
}
sort(g.begin() , g.end());
reverse(g.begin() , g.end());
for(int i=1; i<=n; i++){
p[i] = i;
}
for(int i=0; i<g.size(); i++){
ll x,y;
x = g[i].f;
y = g[i].s;
x = find(x);
y = find(y);
if(x != y){
join1(x,y);
ol[x].pb(y);
ol[y].pb(x);
}
}
dfs(n,0);
timer = 0;
dfs1(1,0);
for(int i=1; i<=q; i++){
s[i] = bigol(s[i] , l[i]);
t[i] = bigne(t[i] , r[i]);
be[in2[s[i]]].pb(i);
ed[out2[s[i]]].pb(i);
}
for(int i=1; i<=2 * n; i++){
for(int j=0; j<be[i].size(); j++)
was[be[i][j]] = cnt(1,1,pown,in1[t[be[i][j]]] , out1[t[be[i][j]]]);
if(tin2[i] != 0){
tt[pown + in1[tin2[i]] - 1]++;
upd((pown + in1[tin2[i]] - 1) / 2);
}
for(int j=0; j < ed[i].size(); j++){
ll now = cnt(1,1,pown,in1[t[ed[i][j]]] , out1[t[ed[i][j]]] );
if(now > was[ed[i][j]])
ans[ed[i][j]] = 1;
}
}
for(int i=1; i<=q; i++)
cout << ans[i] << endl;
return 0;
}
Compilation message
werewolf.cpp: In function 'void dfs(long long int, long long int)':
werewolf.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0; i<ne[x].size(); i++)
| ~^~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs1(long long int, long long int)':
werewolf.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i=0; i<ol[x].size(); i++)
| ~^~~~~~~~~~~~~
werewolf.cpp: In function 'int main()':
werewolf.cpp:122:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int i=0; i<g.size(); i++){
| ~^~~~~~~~~
werewolf.cpp:135:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for(int i=0; i<g.size(); i++){
| ~^~~~~~~~~
werewolf.cpp:147:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int i=0; i<g.size(); i++){
| ~^~~~~~~~~
werewolf.cpp:175:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for(int j=0; j<be[i].size(); j++)
| ~^~~~~~~~~~~~~
werewolf.cpp:182:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
182 | for(int j=0; j < ed[i].size(); j++){
| ~~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccQ6Fo5o.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccx033Jq.o:werewolf.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccQ6Fo5o.o: in function `main':
grader.cpp:(.text.startup+0x377): undefined reference to `check_validity(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
