Submission #823906

#	Time	Username	Problem	Language	Result	Execution time	Memory
823906		tch1cherin	Joker (BOI20_joker)	C++17	100 / 100	561 ms	50548 KiB

Joker

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

struct dsu {
  int size;
  int _bipartite;
  vector<vector<pair<int*, int>>> updates;
  vector<int> parent, rank;

  dsu(int _size) : size(_size), _bipartite(1), parent(2 * _size, -1), rank(2 * _size, 1) {}

  int _get(int u) {
    return parent[u] == -1 ? u : _get(parent[u]);
  }

  void _unite(int u, int v) {
    u = _get(u), v = _get(v);
    if (u != v) {
      if (rank[u] < rank[v]) {
        swap(u, v);
      }
      updates.back().push_back(pair {&parent[v], parent[v]});
      updates.back().push_back(pair {&rank[u], rank[u]});
      parent[v] = u;
      rank[u] += rank[v];
    }
  }

  void unite(int u, int v) {
    updates.push_back({});
    updates.back().push_back(pair {&_bipartite, _bipartite});
    _unite(u, v + size);
    _unite(v, u + size);
    if (_get(u) == _get(u + size)) {
      _bipartite = 0;
    }
    if (_get(v) == _get(v + size)) {
      _bipartite = 0;
    }
  }

  void undo() {
    for (auto &[x, y] : updates.back()) {
      *x = y;
    }
    updates.pop_back();
  }

  bool is_bipartite() {
    return _bipartite > 0;
  }
};

struct dsu_queue {
  struct update {
    int type;
    int u, v;
  };

  int size;
  vector<update> updates;
  int sign;
  int cntA = 0, cntB = 0;
  dsu base;

  dsu_queue(int _size) : size(_size), sign(1), base(_size) {}

  void unite(int u, int v) {
    base.unite(u, v);
    (sign > 0 ? cntA : cntB)++;
    updates.push_back({sign, u, v});
  }

  void undo() {
    if (sign == 1) {
      for (int i = 0; i < (int)updates.size(); i++) {
        base.undo();
      }
      reverse(updates.begin(), updates.end());
      for (auto [type, x, y] : updates) {
        base.unite(x, y);
      }
      sign = -1;
      swap(cntA, cntB);
    }
    vector<update> old_updates, new_updates;
    while (old_updates.size() < new_updates.size() || old_updates.empty()) {
      if (updates.empty()) {
        break;
      }
      if (updates.back().type > 0) {
        old_updates.push_back(updates.back());
      } else {
        new_updates.push_back(updates.back());
      }
      updates.pop_back();
      base.undo();
    }
    for (int i = (int)new_updates.size() - 1; i >= 0; i--) {
      auto [type, x, y] = new_updates[i];
      base.unite(x, y);
      updates.push_back({type, x, y});
    }
    for (int i = (int)old_updates.size() - 1; i > 0; i--) {
      auto [type, x, y] = old_updates[i];
      base.unite(x, y);
      updates.push_back({type, x, y});
    }
    cntA--;
    if (cntA == 0) {
      cntA = cntB;
      for (auto &[type, x, y] : updates) {
        type = 1;
      }
      sign = 1;
    }
  }

  bool is_bipartite() {
    return base.is_bipartite();
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M, Q;
  cin >> N >> M >> Q;
  vector<pair<int, int>> edges(M);
  dsu_queue q(N);
  for (auto &[u, v] : edges) {
    cin >> u >> v;
    u--, v--;
    q.unite(u, v);
  }
  vector<int> R(M);
  for (int i = 0, j = 0; i < M; i++) {
    while (j < M && !q.is_bipartite()) {
      q.undo();
      j++;
    }
    if (q.is_bipartite()) {
      R[i] = j;
    } else {
      R[i] = M + 1;
    }
    if (j > i) {
      q.unite(edges[i].first, edges[i].second);
    }
  }
  for (int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    cout << (R[--l] > r ? "YES\n" : "NO\n");
  }
}

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