Submission #1093574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093574		zNatsumi	Joker (BOI20_joker)	C++17	6 / 100	708 ms	19388 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,
          block = 448;

int n, m, q;
ii edge[N];
bool pre, res[N];
int pa[N], sz[N], lz[N], it;
pair<int*, int> trace[3*N];
vector<tp> que[block + 5];

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

bool uset(int u, int v){
  int cu = 0, cv = 0;
  u = fset(u, cu);
  v = fset(v, cv);
  if(u == v){
    if(cu == cv) return true;
    return false;
  }
  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;
  }
  return false;
}

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

int getblock(int i){
  return (i - 1) / block + 1;
}

void solve(int b, vector<tp> &query){
  if(query.empty()) return;
  int lst = m;
  int flag = it;

  bool val = false;
  for(auto x : query){
    int l, r, idx; tie(r, l, idx) = x;

    if(r <= b*block){
      for(int i = lst; i > b * block; i--) uset(edge[i].fi, edge[i].se);
      int tmp = it;
      bool ok = false;

      for(int i = (b - 1) * block + 1; i <= min(b * block, m); i++){
        if(l <= i && i <= r) continue;

        if(uset(edge[i].fi, edge[i].se)){
          ok = true;
          break;
        }
      }
      res[idx] = ok;
      rollback(tmp);
    }else{
      for(int i = lst; i > r; i--)
        val |= uset(edge[i].fi, edge[i].se);

      lst = r;

      int tmp = it;
      bool dd = false;
      for(int i = (b - 1) * block + 1; i < l; i++) dd |= uset(edge[i].fi, edge[i].se);

      res[idx] = dd | val | pre;
      rollback(tmp);
    }
  }
  rollback(flag);
  for(int i = (b - 1) * block; i <= b * block; i++) pre |= uset(edge[i].fi, edge[i].se);
}


int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }

  cin >> n >> m >> q;
  for(int i = 1; i <= m; i++){
    int u, v; cin >> u >> v;
    edge[i] = {u, v};
  }

  for(int t = 1; t <= q; t++){
    int l, r; cin >> l >> r;
    que[getblock(l)].push_back({r, l, t});
  }
  for(int i = 1; i <= block; i++) sort(all(que[i]), greater<>());
  for(int i = 1; i <= n; i++){
    pa[i] = i;
    sz[i] = 1;
    lz[i] = 0;
  }
  for(int i = 1; i <= block; i++) solve(i, que[i]);

  for(int i = 1; i <= q; i++) cout << (res[i] ? "YES\n" : "NO\n");

  return 0;
}

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