Submission #1102075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102075		epicci23	Joker (BOI20_joker)	C++17	100 / 100	252 ms	16968 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);
 }
 inline int find(int a){
  while(par[a]!=a) a=par[a];
  return a;
 }
 inline int color(int a,int res=0){
  while(par[a]!=a){
    res^=col[a];
    a=par[a];
  }
  return res^col[a];
 }
 inline bool unite(int a,int b){
  int cola=color(a),colb=color(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]=cola^colb^1;
   siz[b]+=siz[a];
   return true;
  }
  else{
    st.push({-1,-1,-1,ok});
    if(cola==colb) ok=0;
    return ok;
  }
 }
 inline 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){
  int mid=(l+r)/2,p=0;

  for(int i=l;i<mid;i++) p++,dsu.unite(v[i][0],v[i][1]);
  
  for(int i=optr;i>=mid;i--){
    p++;
    if(!dsu.unite(v[i][0],v[i][1])){
      last[mid]=i;
      break;
    } 
  }
  while(p>0){
    p--;
    dsu.rollback();
  }
  
  if(mid<r){
    for(int i=l;i<=mid;i++) p++,dsu.unite(v[i][0],v[i][1]);
    f(mid+1,r,max(mid+1,last[mid]),optr);
  }
  while(p>0){
    p--;
    dsu.rollback();
  }
 
  if(l<mid){
    for(int i=optr;i>last[mid];i--) p++,dsu.unite(v[i][0],v[i][1]);
    f(l,mid-1,optl,last[mid]);
  }
  while(p>0){
    p--;
    dsu.rollback();
  }
}

void _(){
  cin >> n >> m >> q;
  last.resize(m+5);
  v.resize(m+5);
  for(int i=1;i<=m;i++) cin >> v[i][0] >> v[i][1];
  
  int p=0,hm=1;
  for(int i=1;i<=m;i++){
    p++;
    if(!dsu.unite(v[i][0],v[i][1])) break;
    hm++;
  }
  while(p>0){
    p--;
    dsu.rollback();
  }  

  for(int i=hm+1;i<=m;i++) last[i]=m+1;
 
  if(hm<=m) f(1,hm,1,m);

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

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

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