Submission #800745

#	Time	Username	Problem	Language	Result	Execution time	Memory
800745		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) {
    g[u][v] = g[v][u] = 0;
    int pu = d.get(u);
    int pv = d.get(v);
    if (pu != pv) {
      vector<int> cur;
      for (int i = 0; i < n; i++) {
        if (d.get(i) == pu) {
          cur.push_back(i);
        }
      }
      set<int> see;
      for (int i = 0; i < n; i++) {
        int pi = d.get(i);
        if (pi == pu) {
          continue;
        }
        for (int uu : cur) {
          if (g[uu][i] != 0) {
            see.insert(pi);
          }
        }
      }
      if (see.empty()) {
        g[u][v] = g[v][u] = 1;
        d.unite(u, v);
      } else {
        cur.clear();
        for (int i = 0; i < n; i++) {
          if (d.get(i) == pv) {
            cur.push_back(i);
          }
        }
        for (int i = 0; i < n; i++) {
          int pi = d.get(i);
          if (pi == pv) {
            continue;
          }
          for (int vv : cur) {
            if (g[vv][i] != 0) {
              see.insert(pi);
            }
          }
        }
        if (see.empty()) {
          d.unite(u, v);
          g[u][v] = g[v][u] = 1;
        }
      }
    }
  }
  return g[u][v];
}

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