This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4,abm,avx,popcnt")
#include<bits/stdc++.h>
//#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define F first
#define S second
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
cout<<a<<" ",debug(b...);
}
const int N=5e5+2;
pii e[N];
int p[N];
int sz[N];
void init(int n){
rep(i,1,n) p[i]=i,sz[i]=1;
}
int fp(int x){
for(;x!=p[x];x=p[x]) ;
return p[x];
}
int ans[N];
stack<tuple<int,int,int>> state;
int n,m;
void _Union(int a,int b){
a=fp(a);
b=fp(b);
if(a==b) {
state.push(make_tuple(-1,-1,-1));
return ;
}
//assert(a!=b);
if(sz[a]<sz[b]) swap(a,b);
state.push(make_tuple(a,sz[a],b));
p[b]=a;
sz[a]+=sz[b];
return ;
}
bool Union(int a,int b){
int fa=fp(a);
int fb=fp(b);
if(fa==fb) return false;
_Union(fa,b+n);
_Union(fb,a+n);
return true;
}
void undo(){
auto [a,sza,b]=state.top();
state.pop();
if(a==-1) return ;
sz[a]=sza;
p[b]=b;
}
void solve(int l,int r,int vl,int vr){
if(l>r||vl>vr) return ;
//debug("solve",l,r,vl,vr);
if(vl==vr){
rep(i,l,r) ans[i]=vl;
return ;
}
int mid=(l+r)>>1;
ans[mid]=vr;
for(int i=mid;i<=vr;i++){
if(i==r+1) i=max(i,vl);
if(!Union(e[i].F,e[i].S)){
ans[mid]=i-1;
break;
}
}
assert(ans[mid]>=vl&&ans[mid]<=vr);
// [r+1,vl-1] is done
for(int i=ans[mid];i>=max(vl,mid);i--){
undo();
undo();
}
solve(l,mid-1,vl,ans[mid]);
rep(i,mid,min(r,vl-1)){
undo();
undo();
}
rep(i,max(r+1,vl),ans[mid]-1) Union(e[i].F,e[i].S);
solve(mid+1,r,ans[mid],vr);
rep(i,max(r+1,vl),ans[mid]-1) undo(),undo();
}
signed main(){
quick
int q;
cin>>n>>m>>q;
init(n*2);
rep(i,0,m-1){
cin>>e[i].F>>e[i].S;
e[i+m]=e[i];
}
solve(0,m,0,m*2-1);
/*rep(i,0,m-1){
cout<<ans[i]<<" \n"[i==m-1];
}
rep(i,0,m-1){
init(2*n);
ans[i]=-1;
rep(j,i,m-1){
if(Union(e[j].F,e[j].S)) ans[i]=j;
else break;
}
cout<<ans[i]<<" \n"[i==m-1];
}*/
string Ans[2]={"YES","NO"};
while(q--){
int l,r;
cin>>l>>r;
--l,--r;
cout<<Ans[(ans[r+1]>=l+m-1)]<<"\n";
}
}
Compilation message (stderr)
Joker.cpp: In function 'void undo()':
Joker.cpp:61:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | auto [a,sza,b]=state.top();
| ^
# | 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... |