#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=2e5+50;
pair<int,int>edges[N];
struct DSU{
int par[N+50],sajz[N+50],bit[N+50];
int bip;
vector<array<int,4>>undo;
DSU(){Clear();}
int FS(int u){if(!par[u])return u;return FS(par[u]);}
int Get(int u){if(!par[u])return 0;return bit[u]^Get(par[u]);}
void US(int u,int v){
int x=Get(u)^Get(v)^1;
u=FS(u),v=FS(v);
if(u!=v){
if(sajz[u]>sajz[v]) swap(u,v);
par[u]=v;
sajz[v]+=sajz[u];
bit[u]=x;
undo.pb({u,v,x,0});
return;
}
bip+=x;
undo.pb({0,0,0,x});
}
void Undo(){
array<int,4>a=undo.back();undo.pop_back();
bip-=a[3];
if(a[0]==0) return;
par[a[0]]=0;
sajz[a[1]]-=sajz[a[0]];
bit[a[0]]=0;
}
void Clear(){for(int i=0;i<=N;i++){par[i]=bit[i]=0;sajz[i]=1;}bip=0;undo.clear();}
}dsu;
int desno[N];
void Solve(int l,int r,int lo,int up){
if(l>r) return;
int mid=l+r>>1;
//printf("%i %i %i %i %i\n",l,mid,r,lo,up);
int cnt1=0,cnt2=0;
for(int i=l;i<mid;i++) dsu.US(edges[i].fi,edges[i].se),cnt1++;
for(int i=up;i>=max(mid,lo);i--){
if(dsu.bip>0){desno[mid]=i;break;}
dsu.US(edges[i].fi,edges[i].se),cnt2++;
}
while(cnt2--) dsu.Undo();
while(cnt1--) dsu.Undo();
if(desno[mid]==0) desno[mid]=mid-1;
for(int i=up;i>desno[mid];i--) dsu.US(edges[i].fi,edges[i].se);
Solve(l,mid-1,lo,desno[mid]);
for(int i=up;i>desno[mid];i--) dsu.Undo();
for(int i=l;i<=mid;i++) dsu.US(edges[i].fi,edges[i].se);
Solve(mid+1,r,desno[mid],up);
for(int i=l;i<=mid;i++) dsu.Undo();
}
int main(){
int n,m,q;scanf("%i%i%i",&n,&m,&q);
for(int i=1,u,v;i<=m;i++){
scanf("%i%i",&u,&v);
edges[i]={u,v};
}
Solve(1,m,1,m);
//for(int i=1;i<=m;i++) printf("%i: %i\n",i,desno[i]);
while(q--){
int l,r;scanf("%i%i",&l,&r);
if(r<=desno[l]) printf("YES\n");
else printf("NO\n");
}
return 0;
}
Compilation message (stderr)
Joker.cpp: In function 'int main()':
Joker.cpp:65:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | int n,m,q;scanf("%i%i%i",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~
Joker.cpp:67:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%i%i",&u,&v);
| ~~~~~^~~~~~~~~~~~~~
Joker.cpp:73:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | int l,r;scanf("%i%i",&l,&r);
| ~~~~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |