Submission #1212250

#TimeUsernameProblemLanguageResultExecution timeMemory
1212250StefanSebezJoker (BOI20_joker)C++20
100 / 100
218 ms9344 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define ll long long #define ld long double const int N=2e5+50; pair<int,int>edges[N]; struct DSU{ int par[N+50],sajz[N+50],bit[N+50]; int bip; vector<array<int,4>>undo; DSU(){Clear();} int FS(int u){if(!par[u])return u;return FS(par[u]);} int Get(int u){if(!par[u])return 0;return bit[u]^Get(par[u]);} void US(int u,int v){ int x=Get(u)^Get(v)^1; u=FS(u),v=FS(v); if(u!=v){ if(sajz[u]>sajz[v]) swap(u,v); par[u]=v; sajz[v]+=sajz[u]; bit[u]=x; undo.pb({u,v,x,0}); return; } bip+=x; undo.pb({0,0,0,x}); } void Undo(){ array<int,4>a=undo.back();undo.pop_back(); bip-=a[3]; if(a[0]==0) return; par[a[0]]=0; sajz[a[1]]-=sajz[a[0]]; bit[a[0]]=0; } void Clear(){for(int i=0;i<=N;i++){par[i]=bit[i]=0;sajz[i]=1;}bip=0;undo.clear();} }dsu; int desno[N]; void Solve(int l,int r,int lo,int up){ if(l>r) return; int mid=l+r>>1; //printf("%i %i %i %i %i\n",l,mid,r,lo,up); int cnt1=0,cnt2=0; for(int i=l;i<mid;i++) dsu.US(edges[i].fi,edges[i].se),cnt1++; for(int i=up;i>=max(mid,lo);i--){ if(dsu.bip>0){desno[mid]=i;break;} dsu.US(edges[i].fi,edges[i].se),cnt2++; } while(cnt2--) dsu.Undo(); while(cnt1--) dsu.Undo(); if(desno[mid]==0) desno[mid]=mid-1; for(int i=up;i>desno[mid];i--) dsu.US(edges[i].fi,edges[i].se); Solve(l,mid-1,lo,desno[mid]); for(int i=up;i>desno[mid];i--) dsu.Undo(); for(int i=l;i<=mid;i++) dsu.US(edges[i].fi,edges[i].se); Solve(mid+1,r,desno[mid],up); for(int i=l;i<=mid;i++) dsu.Undo(); } int main(){ int n,m,q;scanf("%i%i%i",&n,&m,&q); for(int i=1,u,v;i<=m;i++){ scanf("%i%i",&u,&v); edges[i]={u,v}; } Solve(1,m,1,m); //for(int i=1;i<=m;i++) printf("%i: %i\n",i,desno[i]); while(q--){ int l,r;scanf("%i%i",&l,&r); if(r<=desno[l]) printf("YES\n"); else printf("NO\n"); } return 0; }

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:65:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     int n,m,q;scanf("%i%i%i",&n,&m,&q);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
Joker.cpp:67:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |                 scanf("%i%i",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~
Joker.cpp:73:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |                 int l,r;scanf("%i%i",&l,&r);
      |                         ~~~~~^~~~~~~~~~~~~~
#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...