Submission #1186579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186579		versesrev	Game (IOI14_game)	C++20	42 / 100	1096 ms	476 KiB

game

#include <deque>
#include <vector>

int n{};
std::vector<std::vector<bool>> edges;

void initialize(int _n) {
  n = _n;
  edges.assign(n, std::vector<bool>(n, true));
  for (int i = 0; i < n; ++i) {
    edges[i][i] = false;
  }
}

int hasEdge(int u, int v) {
  edges[u][v] = edges[v][u] = false;
  
  std::deque<int> queue;
  std::vector<bool> visited(n);
  int count = 0;
  queue.push_back(u), visited[u] = true, ++count;
  while (not queue.empty()) {
    int cur = queue.front(); queue.pop_front();
    for (int nxt = 0; nxt < n; ++nxt) {
      if (edges[cur][nxt] and not visited[nxt]) {
        queue.push_back(nxt), visited[nxt] = true, ++count;
      }
    }
  }
  
  if (count != n) {
    edges[u][v] = edges[v][u] = true;
  }
  
  return edges[u][v];
}

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