Submission #1232096

#TimeUsernameProblemLanguageResultExecution timeMemory
1232096ender_shayanJoker (BOI20_joker)C++20
0 / 100
9 ms19220 KiB
#include <bits/stdc++.h> using namespace std; // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair<int, int> pii ; typedef pair<ll, ll> pll ; typedef vector<pii> vii ; typedef vector<int> veci ; typedef vector<pll> vll ; typedef vector<ll> vecll; // find_by_order order_of_key //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define F first #define S second #define pb push_back #define endl '\n' #define Mp make_pair #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " = " << x << endl #define set_dec(x) cout << fixed << setprecision(x); #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout); #define lb lower_bound #define ub upper_bound #define for1(n) for(int i=1;i<=n;i++) #define for0(n) for(int i=0;i<n;i++) #define forn(n) for(int i=n;i>0;i--) #define pq priority_queue <pii, vector<pii>, greater<pii>> const int N=2e5+10; int n,m,k,q,c[N],par[N],sz[N],ans[N],mx; vector<int>seg[N*4]; vector<pii> vec; pii edg[N]; int get_par(int v){ if(!par[v])return v; return get_par(par[v]); } int get_c(int v){ if(!par[v])return 0; return get_c(par[v])^c[v]; } void Undo(){ int u=vec.back().F,v=vec.back().S; par[u]=0; sz[v]-=sz[u]; vec.pop_back(); } void merg(int u,int v){ int cc=get_c(u)^get_c(v)^1; u=get_par(u); v=get_par(v); if(u==v)return; if(sz[u]>sz[v])swap(u,v); vec.pb({u,v}); c[u]=cc; par[u]=v; sz[v]+=sz[u]; } void upd(int lx,int rx,int l=1,int r=m+1,int v=1){ if(lx>=r || rx<=l)return; if(lx<=l && r<=rx){ seg[v].pb(rx-1); return; } int mid=(l+r)>>1; upd(lx,rx,l,mid,v<<1); upd(lx,rx,mid,r,v<<1|1); } void dfs(int l=1,int r=m+1,int v=1){ int t=0; for(int i:seg[v])if(get_par(edg[i].F)!=get_par(edg[i].S)){merg(edg[i].F,edg[i].S);t++;} if(r-l==1){ for(;mx<=m;mx++){ int uu=edg[mx].F,vv=edg[mx].S; if(get_par(uu)!=get_par(vv)){ merg(uu,vv); upd(l+1,mx+1); t++; } else if(get_c(uu)!=get_c(vv)) upd(l+1,mx+1); else break; } ans[l]=mx; while(t--)Undo(); return; } int mid=(l+r)>>1; dfs(l,mid,v<<1); dfs(mid,r,v<<1|1); while(t--)Undo(); } int main(){ fast_io cin>>n>>m>>q; for1(n)sz[i]=1; for1(m)cin>>edg[i].F>>edg[i].S; mx=1; dfs(); while(q--){ int l,r;cin>>l>>r; cout<<(r<ans[l] ? "YES\n":"NO\n"); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...