Submission #551767

#TimeUsernameProblemLanguageResultExecution timeMemory
551767oleh1421Joker (BOI20_joker)C++17
14 / 100
2077 ms11708 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=400; 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]; } int cnt=(m+K-1)/K; for (int i=1;i<=cnt;i++){ l[i]=max(m-i*K+1,1); r[i]=m-(i-1)*K; } for (int i=1;i<=n;i++){ dsu[i]=i; sz[i]=1; w[i]=0; } for (int i=1;i<=q;i++){ bool bad=false; int l,r;cin>>l>>r; for (int j=1;j<l;j++){ if (!unite(a[j],b[j])) bad=true; } for (int j=r+1;j<=m;j++){ if (!unite(a[j],b[j])) bad=true; } while (!CH.empty()){ roll_back(); } if (bad) cout<<"YES\n"; else cout<<"NO\n"; } // for (int i=1;i<=cnt;i++){ // bool bad=false; // for (int j=l[i];j<=m;j++){ // if (!unite(a[j],b[j])) bad=true; // } // if (!bad){ // for (int j=1;j<=m;j++){ // if (!unite(a[j],b[j])) break; // group[j]=i; // } // } // while (!CH.empty()){ // roll_back(); // } // } // int last=cnt+1; // for (int i=1;i<=m;i++){ //// cout<<"G "<<i<<" "<<group[i]<<endl; // while (last>group[i]){ // last=group[i]; // while (!CH.empty()){ // roll_back(); // } // for (int j=l[last];j<=m;j++){ // unite(a[j],b[j]); // } // } // unite(a[i],b[i]); // int len=CH.size(); // if (last==cnt) ans[i]=0; // else { // for (int j=r[last+1];j>=l[last+1];j--){ // if (!unite(a[j],b[j])){ // ans[i]=j; // break; // } // } // } // while (CH.size()>len){ // roll_back(); // } // } // // // // // 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...