Submission #252634

#	Time	Username	Problem	Language	Result	Execution time	Memory
252634		ChrisT	Game (IOI14_game)	C++17	100 / 100	487 ms	18808 KiB

game

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1500
int fathers[MAXN];
int connections[MAXN][MAXN];
void initialize (int n) {
  for (int x = 0; x < n; x++) {
    fathers[x] = x;
    for (int y = 0; y < n; y++) connections[x][y] = 1;
    connections[x][x] = 0;
  }
}
int find (int n) {return fathers[n] == n ? n : fathers[n] = find(fathers[n]);}
void merge (int u, int v) {
  fathers[u] = v;
  for (int x = 0; x < MAXN; x++) {
    connections[v][x] += connections[u][x];
    connections[x][v] += connections[u][x];
  }
}
int hasEdge (int u, int v) {
  u = find (u), v = find(v);
  if (v < u) swap(v,u);
  if (connections[u][v] == 1 && connections[v][u] == 1) {
    merge(u,v);
    return 1;
  }
  connections[u][v]--;
  connections[v][u]--;
  return 0;
}

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