Submission #1093791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093791		zNatsumi	Joker (BOI20_joker)	C++17	100 / 100	176 ms	20308 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define tp tuple<int, int, int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()

const int N = 2e5 + 5;

int n, m, q, lst[N], cur = false;
ii edge[N];
int pa[N], sz[N], lz[N], it;
pair<int*, int> trace[3*N];

int fset(int i, int &c){
  c ^= lz[i];
  return i == pa[i] ? i : fset(pa[i], c);
}

void uset(int u, int v){
  int cu = 0, cv = 0;
  u = fset(u, cu);
  v = fset(v, cv);
  if(u == v){
    if(cu == cv){
      trace[it++] = {&cur, cur};
      cur = true;
    }
    return;
  }
  if(sz[u] < sz[v]) swap(u, v);
  trace[it++] = {pa + v, pa[v]}; pa[v] = u;
  trace[it++] = {sz + u, sz[u]}; sz[u] += sz[v];
  if(cu == cv){
    trace[it++] = {lz + v, lz[v]};
    lz[v] ^= 1;
  }
}

void rollback(int t){
  for(; it > t; ){
    it--;
    *trace[it].fi = trace[it].se;
  }
}

void dnc(int l, int r, int optl, int optr){
  if(l > r) return;

  int mid = l + r >> 1,
      ti1 = it,
      opt = m + 1;

  for(int i = l; i < mid; i++) uset(edge[i].fi, edge[i].se);

  int ti2 = it;

  if(!cur){
    for(int i = min(optr, m); i >= max(mid, optl); i--){
      uset(edge[i].fi, edge[i].se);
      opt = i;
      if(cur) break;
    }
  }
  lst[mid] = opt;
  opt = min(opt, m);

  rollback(ti2);
  uset(edge[mid].fi, edge[mid].se);
  dnc(mid + 1, r, opt, optr);

  rollback(ti1);
  for(int i = max(r, optr); i > opt; i--) uset(edge[i].fi, edge[i].se);
  dnc(l, mid - 1, optl, opt);

  rollback(ti1);
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n >> m >> q;
  for(int i = 1; i <= m; i++){
    int u, v; cin >> u >> v;
    edge[i] = {u, v};
  }

  for(int i = 1; i <= n; i++){
    pa[i] = i;
    sz[i] = 1;
    lz[i] = 0;
  }
  dnc(1, m, 1, m);
//  for(int i = 1; i <= m; i++) cout << lst[i] << " \n"[i == m];

  while(q--){
    int l, r; cin >> l >> r;

    cout << (r < lst[l] ? "YES\n" : "NO\n");
  }

  return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void dnc(int, int, int, int)':
Joker.cpp:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |   int mid = l + r >> 1,
      |             ~~^~~

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