제출 #765249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765249		Hegdahl	Joker (BOI20_joker)	C++17	0 / 100	355 ms	3160 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 &[i, j] : edges) {
    cin >> i >> j;
    --i;
    --j;
  }

  UnionFind uf(n);

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

  std::cerr << ans << '\n';

  while (q--) {
    int i, j;
    cin >> i >> j;
    --i;
    --j;

    assert(i == 0);
    if (j < ans) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
}

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