Submission #800729

#	Time	Username	Problem	Language	Result	Execution time	Memory
800729		BERNARB01	Game (IOI14_game)	C++17	0 / 100	6 ms	15956 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

#ifdef B01
#include "../deb.h"
#else
#define deb(...)
#endif

struct dsu {
  vector<int> p;

  dsu() {}

  dsu(int n) {
    p.assign(n, -1);
  }

  inline int get(int x) {
    return (p[x] < 0 ? x : (p[x] = get(p[x])));
  }

  inline void unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (p[x] < p[y]) {
      swap(x, y);
    }
    p[y] += p[x];
    p[x] = y;
  }
};

const int N = 2003;

int n;
dsu d;
int g[N][N];

void initialize(int n_) {
  n = n_;
  d = dsu(n);
  memset(g, -1, sizeof g);
}

int hasEdge(int u, int v) {
  if (g[u][v] != -1) {
    return g[u][v];
  }
  int pu = d.get(u);
  int pv = d.get(v);
  if (pu == pv) {
    g[u][v] = g[v][u] = 0;
    return 0;
  }
  vector<int> l, r;
  for (int i = 0; i < n; i++) {
    int pi = d.get(i);
    if (i != u && pi == pu) {
      l.push_back(i);
    }
    if (i != v && pi == pv) {
      r.push_back(i);
    }
  }
  bool bl = true;
  for (int x : l) {
    for (int y : r) {
      if (g[x][y] != 0) {
        bl = false;
        break;
      }
    }
    if (!bl) {
      break;
    }
  }
  if (bl) {
    g[u][v] = g[v][u] = 1;
    return 1;
  }
  g[u][v] = g[v][u] = 0;
  return 0;
}

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