Submission #1273360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273360		uzukishinobu	Joker (BOI20_joker)	C++20	100 / 100	329 ms	33572 KiB

Joker

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
pair<int,int> z[1000005];
struct node{
      int l,r,t;
};
struct dsu{
      int par[1000005];
      int t[1000005];
      int sz[1000005];
      vector <node> st;
      int sadge=0;
      void init(){
          for (int i=1;i<=a;i++){
              par[i]=i;
              sz[i]=1;
              t[i]=0;
          }
          sadge=1;
      }
      pair<int,int> find(int u){
           if (par[u]==u){
               return {u,0};
           }
           pair<int,int> pre=find(par[u]);
           return {pre.first,pre.second^t[u]};
      }
      void join(int x,int y){
           pair<int,int> pre1=find(x);
           pair<int,int> pre2=find(y);
           x=pre1.first;
           y=pre2.first;
           if (x==y){
               if (pre1.second==pre2.second){
                   st.push_back({sadge,sadge,3});
                   sadge=0;
               }
               return;
           }
           if (sz[x]<sz[y]){
               swap(x,y);
           }
           st.push_back({y,par[y],1});
           st.push_back({x,sz[x],2});
           st.push_back({y,t[y],4});
           par[y]=x;
           sz[x]+=sz[y];
           t[y]=pre1.second^pre2.second^1;
      }
      int get(){
          return st.size();
      }
      void rollback(int x){
           while (st.size()>x){
                 auto [l,r,t1]=st.back();
                 st.pop_back();
                 if (t1==1){
                     par[l]=r;
                 }else if (t1==2){
                     sz[l]=r;
                 }else if (t1==3){
                     sadge=r;
                 }else{
                     t[l]=r;
                 }
           }
      }
};
dsu d;
int res[1000005];

void dnc(int l,int r,int optl,int optr){
//     cerr << l << " " << r << optl << " " << optr  << "\n";
     if (l>r){
        return;
     }
     int snapshot=d.get();
     int mid=(l+r)/2;
     for (int i=l;i<mid;i++){
          d.join(z[i].first,z[i].second);
     }
     bool check=false;
     int pos=optr;
     for (int i=optr;i>=max(mid,optl);i--){
          if (d.sadge){
              check=true;
              pos=i;
          }else{
              break;
          }
          d.join(z[i].first,z[i].second);
     }
     if (check){
         res[mid]=pos;
     }else{
         res[mid]=b+1;
     }
     d.rollback(snapshot);
     for (int i=optr;i>pos;i--){
          d.join(z[i].first,z[i].second);
     }
     dnc(l,mid-1,optl,pos);
     d.rollback(snapshot);
     for (int i=l;i<=mid;i++){
          d.join(z[i].first,z[i].second);
     }
     dnc(mid+1,r,pos,optr);
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> c;
    for (int i=1;i<=b;i++){
         int x,y;
         cin >> x >> y;
         z[i]={x,y};
    }
    d.init();
    dnc(1,b,1,b);
    for (int i=1;i<=c;i++){
          int x,y;
          cin >> x >> y;
          if (res[x]>y){
              cout << "YES" << "\n";
          }else{
              cout << "NO" << "\n";
          }
    }
    return 0;
}

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