Submission #885537

#	Time	Username	Problem	Language	Result	Execution time	Memory
885537		huutuan	Joker (BOI20_joker)	C++14	100 / 100	425 ms	35900 KiB

Joker

#include<bits/stdc++.h>
#define taskname "nohome"

using namespace std;

struct DSU{
   vector<int> lab, val;
   bool ans=1;
   vector<vector<pair<int, int>>> changes;
   void init(int n){
      lab.assign(n+1, -1);
      val.assign(n+1, 0);
   }
   pair<int, int> find_set(int u){
      if (lab[u]<0) return {u, 0};
      auto p=find_set(lab[u]);
      return {p.first, val[u]^p.second};
   }
   void union_sets(int u, int v){
      if (!u || !v) return;
      auto pu=find_set(u), pv=find_set(v);
      if (pu.first!=pv.first){
         if (lab[pu.first]>lab[pv.first]) swap(pu, pv), swap(u, v);
         changes.push_back({{pu.first, lab[pu.first]}, {pv.first, lab[pv.first]}, {pu.first, val[pu.first]}, {pv.first, val[pv.first]}});
         lab[pu.first]+=lab[pv.first];
         val[pu.first]=0;
         lab[pv.first]=pu.first;
         val[pv.first]=pu.second^pv.second^1;
      }else changes.push_back({{ans, -1}}), ans&=pu.second^pv.second;
   }
   void rollback(int sz){
      while ((int)changes.size()>sz){
         if (changes.back().size()==1){
            ans=changes.back()[0].first;
         }else{
            for (int i=0; i<2; ++i) lab[changes.back()[i].first]=changes.back()[i].second;
            for (int i=2; i<4; ++i) val[changes.back()[i].first]=changes.back()[i].second;
         }
         changes.pop_back();
      }
   }
} dsu;

const int N=2e5+1;
int n, m, q, ans[N], mx[N];
pair<int, int> edge[N];

void dnc(int l, int r, int optl, int optr){
   if (l>r) return;
   int mid=(l+r)>>1;
   int sz=dsu.changes.size();
   int idx=optr;
   for (int i=l; i<mid; ++i) dsu.union_sets(edge[i].first, edge[i].second);
   int sz2=dsu.changes.size();
   while (dsu.ans && idx>=optl){
      dsu.union_sets(edge[idx].first, edge[idx].second);
      --idx;
   }
   mx[mid]=idx;
   dsu.rollback(sz2);
   dsu.union_sets(edge[mid].first, edge[mid].second);
   dnc(mid+1, r, idx, optr);
   dsu.rollback(sz);
   for (int i=idx+1; i<=optr; ++i) dsu.union_sets(edge[i].first, edge[i].second);
   dnc(l, mid-1, optl, idx);
   dsu.rollback(sz);
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   // freopen(taskname".inp", "r", stdin);
   // freopen(taskname".out", "w", stdout);
   cin >> n >> m >> q;
   for (int i=1; i<=m; ++i){
      int x, y; cin >> x >> y;
      edge[i]={x, y};
   }
   dsu.init(n);
   dnc(1, m, 0, m);
   for (int i=1; i<=q; ++i){
      int l, r; cin >> l >> r;
      cout << (mx[l]>=r?"YES\n":"NO\n");
   }
   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