제출 #1186587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186587		versesrev	게임 (IOI14_game)	C++20	42 / 100	1093 ms	756 KiB

game

#include <deque>
#include <vector>
#include <bitset>

constexpr int N = 1500;
int n{};
std::bitset<N> mask;
std::vector<std::bitset<N>> edges;

void initialize(int _n) {
  n = _n;
  edges.assign(n, {});
  for (int i = 0; i < n; ++i) mask[i] = true;
  for (int i = 0; i < n; ++i) {
    edges[i] = ~edges[i] & mask;
  }
}

int hasEdge(int u, int v) {
  edges[u][v] = edges[v][u] = false;
  
  std::bitset<N> not_visited = mask;
  std::bitset<N> new_vs;
  new_vs[u] = true;
  while (new_vs.any() and not_visited[v]) {
    not_visited &= ~new_vs;
    std::bitset<N> next_new_vs;
    for (int i = 0; i < n; ++i) {
      if (new_vs[i]) {
        next_new_vs |= edges[i] & not_visited;
      }
    }
    std::swap(new_vs, next_new_vs);
  }
  
  if (not_visited[v]) {
    edges[u][v] = edges[v][u] = true;
  }
  
  return edges[u][v];
}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 0 / 58