#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"
// ==========================(debug)============================================================================================== //
#ifdef SAMI
#define debug(x) cerr<<#x;cerr<<" ";_printn(x);cerr<<nli;
#define debg() cerr<<nli;
#else
#define debug(x)
#define debg()
#endif
void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
// ==========================(debug)============================================================================================== //
ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 2e5+5;
const ll mod = 1e9+7;
// ==========================(MOD)=============================================================================================== //
ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }
// ==========================(MOD)=============================================================================================== //
bool f = false;
ll from[mx];
ll to[mx];
ll lst[mx];
typedef struct Disjoint_Set_Union{
vi par,sz,cos,mark;
ll range,rs,src,dest;
ll c1,c2;
vector<vector<int>> lis;
void init(ll k){
k += 5;
par.resize(k);
sz.resize(k);
cos.resize(k);
f = 0;
fip(0,k){
par[i] = i;
sz[i] = 1;
cos[i] = 0;
}
}
ll find(ll k){
while(k!=par[k]){
k = par[k];
}
return k;
}
ll get(ll k){
rs = cos[k];
while(k!=par[k]){
k = par[k];
rs ^= cos[k];
}
return rs;
}
bool unite(ll u,ll v){
src = find(u);
dest = find(v);
c1 = get(u);
c2 = get(v);
if(src==dest){
if(c1==c2 && !f){
f = 1;
lis.push_back({-1});
}
return 0;
}
if(sz[src] < sz[dest]){
swap(c1,c2);
swap(src,dest);
}
lis.push_back({(int)dest,(int)par[dest],(int)cos[dest]});
par[dest] = src;
cos[dest] ^= c1^c2^1;
sz[src] += sz[dest];
return 1;
}
void rollback(ll k){
while((ll)lis.size()>k){
auto it = lis.back();
lis.pop_back();
if(it[0]==-1)
f = 0;
else{
sz[par[it[0]]] -= sz[it[0]];
cos[it[0]] = it[2];
par[it[0]] = it[1];
}
}
return;
}
void destroy(){
lis.clear();
}
}DSU;
DSU dsu;
ll mid;
ll st,en;
void divide(ll l1,ll l2,ll r1,ll r2){
if(l1>l2)
return;
debug(l1);
debug(l2);
debug(r1);
debug(r2);
ll pt2 = dsu.lis.size();
mid = l1 + (l2-l1)/2;
while(l1 > st){
dsu.unite(from[st],to[st]);
st++;
}
while(r2 < en){
dsu.unite(from[en],to[en]);
en--;
}
debug(f);
ll pt = dsu.lis.size();
debug(dsu.lis);
while(mid > st){
dsu.unite(from[st],to[st]);
// debug(f);
st++;
}
fin(r2,r1){
if(f){
lst[mid] = i;
break;
}
if(i<m){
dsu.unite(from[i],to[i]);
// debug(f)
if(f){
lst[mid] = i;
break;
}
}
}
debug(dsu.lis);
dsu.rollback(pt);
st = l1;
en = r2;
if(en==m)en--;
debug(mid);
debug(lst[mid])
debg() ;
divide(l1,mid-1,r1,lst[mid]);
divide(mid+1,l2,lst[mid],r2);
st = l1;
en = r2;
if(en==m)en--;
dsu.rollback(pt2);
return;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef SAMI
freopen("input1.txt", "r", stdin);
freopen("output1.txt", "w", stdout);
freopen("error1.txt", "w", stderr);
#endif // ONLINE_JUDGE
cin>>n>>m>>tptp;
fip(0,m)
cin>>from[i]>>to[i];
dsu.init(n);
st = 0;
en = m-1;
divide(0,m-1,0,m);
// fip(0,m)
// cout<<lst[i]<<" ";
// cout<<nli;
fip(0,tptp) {
cin>>tp>>tp2;
tp--,tp2--;
cout<<(lst[tp]>tp2?"YES":"NO")<<nli;
}
cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
# | 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... |