Submission #261668

#	Time	Username	Problem	Language	Result	Execution time	Memory
261668		rama_pang	Joker (BOI20_joker)	C++14	100 / 100	472 ms	18132 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int N, M, Q;
pair<int, int> edges[MAXN];

// Disjoint Set with rollbacks
int par[MAXN * 2];
int sz[MAXN * 2];

vector<pair<int, int>> hist;

int Find(int x) {
  return par[x] == x ? x : Find(par[x]);
}

int Unite(int x, int y) {
  x = Find(x), y = Find(y);
  if (x == y) return 0;
  if (sz[x] > sz[y]) swap(x, y);
  hist.emplace_back(x, par[x]);
  hist.emplace_back(y, sz[y]);
  par[x] = y;
  sz[y] += sz[x];
  return 1;
}

void Rollback(int x) {
  while (x--) {
    sz[hist.back().first] = hist.back().second;
    hist.pop_back();
    par[hist.back().first] = hist.back().second;
    hist.pop_back();
  }
}

int last[MAXN]; // last[L] = highest R, such that erasing edges = [L...R), odd cycle still exist

void FindOpt(int ll, int lr, int rl, int rr) {
  if (ll > lr) return;
  int l = (ll + lr) / 2;
  int r = rr;
  int ops = 0;
  int odd_cycle = 0;
  for (int i = ll; i < l; i++) {
    ops += Unite(edges[i].first + MAXN, edges[i].second);
    ops += Unite(edges[i].first, edges[i].second + MAXN);    
    if (Find(edges[i].first) == Find(edges[i].first + MAXN)) {
      odd_cycle = 1;
      Rollback(ops); ops = 0;
      last[l] = r = M + 1;
      break;
    }
  }
  for (int i = rr; odd_cycle == 0 && i >= max(l, rl); i--) {
    ops += Unite(edges[i].first + MAXN, edges[i].second);
    ops += Unite(edges[i].first, edges[i].second + MAXN);
    if (Find(edges[i].first) == Find(edges[i].first + MAXN)) {
      last[l] = r = i;
      Rollback(ops); ops = 0;
      break;
    }
  }

  odd_cycle = 0;
  for (int i = r + 1; i <= rr; i++) {
    ops += Unite(edges[i].first + MAXN, edges[i].second);
    ops += Unite(edges[i].first, edges[i].second + MAXN);
    if (Find(edges[i].first) == Find(edges[i].first + MAXN)) {
      odd_cycle = 1;
      Rollback(ops); ops = 0;
      for (int j = ll; j < l; j++) {
        last[j] = M + 1;
      }
      break;
    }
  }
  if (odd_cycle == 0) {
    FindOpt(ll, l - 1, rl, r);
    Rollback(ops); ops = 0;
  }

  odd_cycle = 0;
  for (int i = ll; i <= l; i++) {
    ops += Unite(edges[i].first + MAXN, edges[i].second);
    ops += Unite(edges[i].first, edges[i].second + MAXN);
    if (Find(edges[i].first) == Find(edges[i].first + MAXN)) {
      odd_cycle = 1;
      Rollback(ops); ops = 0;
      for (int j = l + 1; j <= lr; j++) {
        last[j] = M + 1;
      }
      break;
    } 
  }
  if (odd_cycle == 0) {
    FindOpt(l + 1, lr, r, rr);
    Rollback(ops); ops = 0;
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  iota(par, par + MAXN * 2, 0);
  fill(sz, sz + MAXN * 2, 1);

  cin >> N >> M >> Q;
  for (int i = 1; i <= M; i++) {
    cin >> edges[i].first >> edges[i].second;
  }
  edges[M + 1].first = N + 1, edges[M + 1].second = N + 2;
  FindOpt(1, M, 1, M + 1);
  for (int i = 1; i <= Q; i++) {
    int l, r;
    cin >> l >> r;
    if (r < last[l]) {
      cout << "YES\n";
    } else {
      cout << "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