Submission #349736

#	Time	Username	Problem	Language	Result	Execution time	Memory
349736		Pety	Game (IOI14_game)	C++14	100 / 100	509 ms	25324 KiB

game

#include <bits/stdc++.h>


using namespace std;

int n, sz[2000], p[2000], cnt[1502][1502];

int find (int x) {
  if (p[x] == x)
    return x;
  return p[x] = find(p[x]);
}

void Union (int x, int y) {
  if (x != y) {
    if (sz[x] < sz[y])
      swap(x, y);
    for (int i = 1; i <= n; i++) {
      cnt[i][x] += cnt[i][y];
      cnt[x][i] += cnt[i][y];
    }
    p[y] = x;
  }
  return;
}

void initialize(int m) {
  n = m;
  for (int i = 1; i <= n; i++)  {
    sz[i] = 1;
    p[i] = i;
    for (int j = 1; j <= n; j++)
      cnt[i][j] = (i != j);
  }
}

int hasEdge (int x, int y) {
  x++;y++;
  x = find(x);
  y = find(y);
  if (x == y)
    return 0;
  if (cnt[x][y] > 1) {
    cnt[x][y]--;
    cnt[y][x]--;
    return 0;
  }
  Union(x, y);
  return 1;
}

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