Submission #765484

#	Time	Username	Problem	Language	Result	Execution time	Memory
765484		Hegdahl	Joker (BOI20_joker)	C++17	100 / 100	1926 ms	12444 KiB

Joker

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

struct UnionFind {
  vector<int> parent_or_neg_size, edge_parity;
  struct UndoInfo {
    int i, j, j_sz;
  };
  vector<UndoInfo> undo_info;

  UnionFind(int n) : parent_or_neg_size(n, -1),
                     edge_parity(n, 0) {}

  pair<int, int> find_root_and_parity(int i) {
    int parity = 0;
    while (parent_or_neg_size[i] >= 0) {
      parity ^= edge_parity[i];
      i = parent_or_neg_size[i];
    }
    return {i, parity};
  }

  int path_compressing_find(int i) {
    if (parent_or_neg_size[i] < 0) {
      edge_parity[i] = 0;
      return i;
    }

    int new_parent = path_compressing_find(parent_or_neg_size[i]);
    edge_parity[i] ^= edge_parity[parent_or_neg_size[i]];
    return parent_or_neg_size[i] = new_parent;
  }

  enum UniteResult { NO_CYCLE, EVEN_CYCLE, ODD_CYCLE };
  UniteResult persistent_unite(int i, int j, bool new_edge_parity = true) {
    auto [root_i, parity_i] = find_root_and_parity(i);
    auto [root_j, parity_j] = find_root_and_parity(j);
    if (root_i == root_j) {
      undo_info.push_back({0, 0, 0});

      if (parity_i ^ parity_j ^ new_edge_parity) {
        return ODD_CYCLE;
      } else {
        return EVEN_CYCLE;
      }
    }
    if (parent_or_neg_size[root_i] > parent_or_neg_size[root_j]) {
      swap(root_i, root_j);
      swap(parity_i, parity_j);
    }

    undo_info.push_back({
        .i = root_i,
        .j = root_j,
        .j_sz = parent_or_neg_size[root_j],
    });

    parent_or_neg_size[root_i] += parent_or_neg_size[root_j];
    parent_or_neg_size[root_j] = root_i;
    edge_parity[root_j] = parity_i ^ parity_j ^ new_edge_parity;

    return NO_CYCLE;
  }

  UniteResult fast_unite(int i, int j, bool new_edge_parity = true) {
    int pi = path_compressing_find(i);
    int pj = path_compressing_find(j);
    if (pi == pj) {
      if (edge_parity[i] ^ edge_parity[j] ^ new_edge_parity) {
        return ODD_CYCLE;
      } else {
        return EVEN_CYCLE;
      }
    }

    if (parent_or_neg_size[pi] > parent_or_neg_size[pj]) {
      swap(pi, pj);
      swap(i, j);
    }

    parent_or_neg_size[pi] += parent_or_neg_size[pj];
    parent_or_neg_size[pj] = pi;
    edge_parity[pj] = edge_parity[i] ^ edge_parity[j] ^ new_edge_parity;

    return NO_CYCLE;
  }

  void undo() {
    assert(!undo_info.empty());
    auto [i, j, j_sz] = undo_info.back();
    undo_info.pop_back();
    if (i == 0 && j == 0) {
      return;
    }

    parent_or_neg_size[j] = j_sz;
    parent_or_neg_size[i] -= j_sz;
  }

  void undo_all() {
    while (!undo_info.empty()) {
      undo();
    }
  }
};

int main() {
  int n, m, q;
  cin >> n >> m >> q;

  vector<array<int, 2>> edges(m);
  for (auto &[u, v] : edges) {
    cin >> u >> v;
    --u;
    --v;
  }

  static constexpr auto BLOCK_SIZE = 400;

  std::vector<array<int, 2>> queries(q);
  std::vector<std::basic_string<int>> blocks((m + BLOCK_SIZE - 1) / BLOCK_SIZE);
  std::vector<bool> answers(q);
  for (int qq = 0; qq != q; ++qq) {
    auto &[l, r] = queries[qq];
    cin >> l >> r;
    --l;
    blocks[l / BLOCK_SIZE].push_back(qq);
  }

  UnionFind uf(n);
  for (int lid = 0; lid != int(blocks.size()); ++lid) {
    uf.parent_or_neg_size.assign(n, -1);

    std::sort(blocks[lid].begin(), blocks[lid].end(), [&](int i, int j) {
      auto &[l0, r0] = queries[i];
      auto &[l1, r1] = queries[j];
      return r0 > r1;
    });

    int min_l = lid * BLOCK_SIZE;

    bool base_has_odd_cycle = false;

    for (int j = 0; j != min_l; ++j) {
      auto [u, v] = edges[j];
      if (uf.fast_unite(u, v) == UnionFind::ODD_CYCLE) {
        base_has_odd_cycle = true;
        break;
      }
    }

    int last_added = m;
    for (int qq : blocks[lid]) {
      auto &[l, r] = queries[qq];
      while (!base_has_odd_cycle && r < last_added) {
        auto [u, v] = edges[--last_added];
        if (uf.fast_unite(u, v) == UnionFind::ODD_CYCLE) {
          base_has_odd_cycle = true;
        }
      }

      bool has_odd_cycle = base_has_odd_cycle;
      for (int j = min_l; !has_odd_cycle && j != l; ++j) {
        auto [u, v] = edges[j];
        if (uf.persistent_unite(u, v) == UnionFind::ODD_CYCLE) {
          has_odd_cycle = true;
        }
      }

      answers[qq] = has_odd_cycle;
      uf.undo_all();
    }
  }

  for (bool answer : answers) {
    cout << (answer ? "YES" : "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