Submission #1101817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101817		epicci23	Joker (BOI20_joker)	C++17	0 / 100	261 ms	21108 KiB

Joker

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 2e5 + 5;

struct DSU{
 int n;
 stack<array<int,4>> st;
 vector<int> par,siz,col;
 bool ok=1;
 DSU(int _n){
  n=_n+5;
  par.assign(n,0);
  col.assign(n,0);
  iota(all(par),0);
  siz.assign(n,1);
 }
 int find(int a){
  while(par[a]!=a) a=par[a];
  return a;
 }
 int color(int a){
  if(par[a]==a) return col[a];
  return col[a]^color(par[a]);
 }
 void unite(int a,int b){
  if(find(a)!=find(b)){
   a=find(a),b=find(b);
   if(siz[a]>siz[b]) swap(a,b);
   st.push({a,b,siz[a],col[a]});
   par[a]=b;
   col[a]=col[a]^col[b]^1;
   siz[b]+=siz[a];
  }
  else{
    st.push({-1,-1,-1,ok});
    if(color(a)==color(b)) ok=0;
  }
 }
 void rollback(){
   if(st.empty()) return;
   array<int,4> c = st.top();
   st.pop();
   if(c[0]==-1) ok=c[3];
   else{
    par[c[0]]=c[0];
    col[c[0]]=c[3];
    siz[c[1]]-=c[2];
   }
 }
};

vector<array<int,2>> v;
vector<int> last;
int n,m,q;
DSU dsu(N);

void f(int l,int r,int optl,int optr){
  if(l>r) return;
  int mid=(l+r)/2,p=0;

  for(int i=l;i<mid;i++){
    p++;
    dsu.unite(v[i][0],v[i][1]);
  }

  if(dsu.ok==0) last[mid]=optr+1;
  else{
   for(int i=optr;i>mid;i--){
     dsu.unite(v[i][0],v[i][1]);
     p++;
     if(dsu.ok==0){
      last[mid]=i;
      break;
     }  
    }
    if(dsu.ok==1) last[mid]=mid;
  }
  //cout << "hesaplandi: " << mid << ' ' << last[mid] << '\n';
  while(p>0){
    p--;
    dsu.rollback();
  }
  for(int i=optr;i>last[mid];i--){
    p++;
    dsu.unite(v[i][0],v[i][1]);
  }
  f(l,mid-1,optl,min(optr,last[mid]));
  while(p>0){
    p--;
    dsu.rollback();
  }
  for(int i=l;i<=mid;i++){
    p++;
    dsu.unite(v[i][0],v[i][1]);
  }
  f(mid+1,r,min(optr,last[mid]),optr);
  while(p>0){
    p--;
    dsu.rollback();
  }
}

void _(){
  cin >> n >> m >> q;
  last.resize(m+5);
  for(int i=1;i<=n;i++) last[i]=i;
  v.resize(m+5);
  for(int i=1;i<=m;i++) cin >> v[i][0] >> v[i][1];
  
  f(1,m,1,m);

  while(q--){
    int l,r;
    cin >> l >> r;
    if(r<last[l]) cout << "YES\n";
    else cout << "NO\n";
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29