Submission #765272

#	Time	Username	Problem	Language	Result	Execution time	Memory
765272		Hegdahl	Joker (BOI20_joker)	C++17	39 / 100	362 ms	7728 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

struct UnionFind {
  vector<int> parent_or_neg_size, edge_parity;

  UnionFind(int n) : parent_or_neg_size(n, -1), // hver komponent har til å begynne med størrelse 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};
  }

  enum UniteResult { NO_CYCLE, EVEN_CYCLE, ODD_CYCLE };
  UniteResult 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) {
      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);
    }
    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;
  }
};

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;
  }

  if ((long long)n * q <= 1e7) {
    while (q--) {
      int l, r;
      cin >> l >> r;
      --l;

      UnionFind uf(n);
      bool odd = false;
      for (int j = 0; j < l; ++j) {
        auto [u, v] = edges[j];
        if (uf.unite(u, v) == UnionFind::ODD_CYCLE) {
          odd = true;
          break;
        }
      }

      for (int j = r; j < m; ++j) {
        auto [u, v] = edges[j];
        if (uf.unite(u, v) == UnionFind::ODD_CYCLE) {
          odd = true;
          break;
        }
      }

      cout << (odd ? "YES" : "NO") << '\n';
    }
  } else {

    int ans = m;
    UnionFind uf(n);
    while (ans) {
      auto [u, v] = edges[ans - 1];
      if (uf.unite(u, v) == UnionFind::ODD_CYCLE) {
        break;
      }
      --ans;
    }

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

      if (r < ans) {
        cout << "YES\n";
      } else {
        cout << "NO\n";
      }
    }
  }
}

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