Submission #798009

#	Time	Username	Problem	Language	Result	Execution time	Memory
798009		erray	Game (IOI14_game)	C++17	100 / 100	293 ms	25172 KiB

game

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

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/codes/ioi14_d1/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename T> 
vector<T> inverse_fuck(T* a, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = a[i];
  }
  return res;
}

template<typename T> 
T* fuck(vector<T> a) {
  T res[int(a.size())];
  for (int i = 0; i < int(a.size()); ++i) {
    res[i] = a[i];
  }
  return res;
}





struct DSU {
  vector<int> link;
  vector<int> size;
  DSU() { }
  DSU(int n) {
    link.resize(n);
    size.resize(n, 1);
    iota(link.begin(), link.end(), 0);
  }
  int get(int x) {
    return link[x] = (x == link[x] ? x : get(link[x]));
  }
  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) {
      return false;
    }
    link[y] = x;
    size[x] += size[y];
    return true;
  }
};
int n;
vector<vector<int>> deg;
DSU d;

void initialize(int _n) {
  n = _n;
  deg.resize(n, vector<int>(n));
  d = DSU(n);

}

int hasEdge(int u, int v) {
  debug(u, v);
  u = d.get(u), v = d.get(v);
  assert(u != v);
  int need = d.size[u] * d.size[v] - 1;
  int has = max(deg[v][u], deg[u][v]);
  debug(need, has);
  if (has == need) {
    d.unite(v, u);
    vector<int> next(n);
    for (int i = 0; i < n; ++i) {
      int to = d.get(i);
      next[to] += deg[v][i] + deg[u][i];
    }
    swap(deg[v], next);
    return true;
  } else {
    deg[v][u] += 1;
    deg[u][v] += 1;
    return false;
  }
}

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