Submission #300052

#	Time	Username	Problem	Language	Result	Execution time	Memory
300052		kevlee	Game (IOI14_game)	C++17	100 / 100	518 ms	25340 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
int comp[1505], sz[1505], link[1505][1505];
int n;
void initialize(int N) {  
  n = N;
  FOR(i, 1, n) comp[i] = i, sz[i] = 1;
  FOR(i, 1, n) {
    FOR(j, 1, n) {
      if (i != j) link[i][j] = 1;
    }
  }
  return;
}
int hasEdge(int u, int v) {
  u++;
  v++;
  if (link[comp[u]][comp[v]] == 1) {
    FOR(i, 1, n) {
      if (comp[i] != comp[v] && comp[i] != comp[u] && comp[i] == i) {
        link[comp[i]][comp[v]] += link[comp[i]][comp[u]];
        link[comp[v]][comp[i]] += link[comp[i]][comp[u]];
      }
    }
    sz[comp[v]] += sz[comp[u]];
    int tmp = comp[u];
    FOR(i, 1, n) {
      if (comp[i] == tmp) comp[i] = comp[v];
    }
    return 1;
  }
  link[comp[u]][comp[v]]--;
  link[comp[v]][comp[u]]--;
  return 0;
}

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