Submission #1095608

#TimeUsernameProblemLanguageResultExecution timeMemory
1095608simona1230Joker (BOI20_joker)C++17
0 / 100
306 ms19872 KiB
#include <bits/stdc++.h> using namespace std; int n,m,k; pair<int,int> e[200001],q[200001]; void read() { cin>>n>>m>>k; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; e[i]={x,y}; } for(int i=1;i<=k;i++) { int l,r; cin>>l>>r; q[i]={l,r}; } } struct event { int x,y; pair<int,int> p; event(){} event(int _x,int _y,pair<int,int> _p) { x=_x; y=_y; p=_p; } }; pair<int,int> p[200001]; stack<event> s; int sz[200001]; void rollback() { event t=s.top(); s.pop(); p[t.x]=t.p; sz[t.y]-=sz[t.x]; } pair<int,int> parent(int x) { if(x==p[x].first)return p[x]; pair<int,int> curr=parent(p[x].first); curr.second+=p[x].second; return curr; } void unite(int x,int y,int&cnt, bool&cyc) { //cout<<x<<" "<<y<<endl; pair<int,int> px=parent(x); pair<int,int> py=parent(y); x=px.first; y=py.first; if(x!=y) { if(sz[x]>sz[y])swap(x,y); s.push({x,y,p[x]}); p[x]={y,px.second+py.second+1}; sz[y]+=sz[x]; cnt++; } else { if(px.second%2==py.second%2) { //cout<<"hje"<<endl; cyc=1; } } } int c[200001]; void rec(int l,int r,int optl,int optr) { if(l>r)return; //cout<<l<<" "<<r<<" "<<optl<<" "<<optr<<endl; if(optl==optr) { for(int i=l;i<=r;i++) c[i]=optr; return; } int mid=(l+r)/2; int cnt1=0; bool ans=0; for(int i=l;i<mid;i++) unite(e[i].first,e[i].second,cnt1,ans); int j=optr; int cnt2=0; while(!ans&&j>=optl) { if(j!=m+1) unite(e[j].first,e[j].second,cnt2,ans); j--; } j++; while(cnt2) { cnt2--; rollback(); } while(cnt1) { cnt1--; rollback(); } c[mid]=j; //cout<<"! "<<mid<<" "<<j<<endl; ans=0; int cnt3=0; for(int i=j+1;i<=min(m,optr);i++) unite(e[i].first,e[i].second,cnt3,ans); if(ans)rec(l,mid-1,j,j); else rec(l,mid-1,optl,j); while(cnt3) { cnt3--; rollback(); } ans=0; int cnt4=0; for(int i=l;i<=mid;i++) unite(e[i].first,e[i].second,cnt4,ans); if(ans)rec(mid+1,r,optr,optr); else rec(mid+1,r,j,optr); while(cnt4) { cnt4--; rollback(); } } void solve() { for(int i=1;i<=k;i++) { if(q[i].second<c[q[i].first])cout<<"YES"<<endl; else cout<<"NO"<<endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); read(); for(int i=1;i<=n;i++) p[i]={i,0},sz[i]=1; rec(1,m,1,m+1); solve(); return 0; } /* 6 8 2 1 3 1 5 1 6 2 5 2 6 3 4 3 5 5 6 1 8 8 8 */
#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...