제출 #765267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765267		Hegdahl	Joker (BOI20_joker)	C++17	14 / 100	2053 ms	5144 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;
  }

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

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