Submission #551792

#TimeUsernameProblemLanguageResultExecution timeMemory
551792oleh1421Joker (BOI20_joker)C++17
0 / 100
473 ms262144 KiB
//#pragma GCC target("avx2") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> //#define endl '\n' using namespace __gnu_pbds; typedef long double ld; //#define int ll using namespace std; mt19937 rnd(time(NULL)); typedef long long ll; const int N=400100; const int K=200010; int a[N],b[N]; int ans[N]; int l[N/K+1]; int r[N/K+1]; int group[N]; int w[N]; int sz[N]; int dsu[N]; vector<pair<int,pair<int,int> > >CH; pair<int,int>get(int x){ if (x==dsu[x]) return {x,w[x]}; auto cur=get(dsu[x]); cur.second^=w[x]; return cur; } bool unite(int a,int b){ auto x=get(a); auto y=get(b); if (x.first==y.first){ return (x.second!=y.second); } if (sz[x.first]>sz[y.first]) swap(x,y); CH.push_back({1,{x.first,dsu[x.first]}}); CH.push_back({2,{y.first,sz[y.first]}}); CH.push_back({3,{x.first,w[x.first]}}); dsu[x.first]=y.first; sz[y.first]+=sz[x.first]; w[x.first]^=(x.second^y.second^1^w[y.first]); return true; } void roll_back(){ if (!CH.empty()){ auto cur=CH.back(); CH.pop_back(); if (cur.first==1) dsu[cur.second.first]=cur.second.second; else if (cur.first==2) sz[cur.second.first]=cur.second.second; else w[cur.second.first]=cur.second.second; } } void solve(){ int n,m,q;cin>>n>>m>>q; for (int i=1;i<=m;i++){ cin>>a[i]>>b[i]; } bool bad=false; for (int i=1;i<=m;i++){ bad=false; for (int i=1;i<=n;i++){ dsu[i]=i; sz[i]=1; w[i]=0; } for (int j=1;j<=i;j++){ if (!unite(a[j],b[j])) bad=true; } if (bad) ans[i]=m+1; else { ans[i]=0; for (int j=m;j>=1;j--){ if (!unite(a[j],b[j])){ ans[i]=j; break; } } } } for (int i=1;i<=q;i++){ int l,r;cin>>l>>r; if (ans[l-1]<=r) cout<<"NO\n"; else cout<<"YES\n"; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int tt=1; while (tt--){ solve(); } return 0; } /** 6 8 2 1 3 1 5 1 6 2 5 2 6 3 4 3 5 5 6 4 8 4 7 **/
#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...