Submission #169446

#	Time	Username	Problem	Language	Result	Execution time	Memory
169446		AlexLuchianov	Game (IOI14_game)	C++14	100 / 100	497 ms	25188 KiB

game

#include "game.h"

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 1500;
int coef[1 + nmax][1 + nmax];
int n;

namespace Dsu{
  int mult[1 + nmax];
  int sz[1 + nmax];
  void init(){
    for(int i = 0;i < n; i++)
      mult[i] = i;
    for(int i = 0;i < n; i++)
      sz[i] = 1;
  }
  int jump(int gala){
    if(mult[gala] != gala)
      mult[gala] = jump(mult[gala]);
    return mult[gala];
  }
  void unite(int gala, int galb){
    gala = jump(gala);
    galb = jump(galb);
    sz[galb] += sz[gala];
    for(int i = 0; i < n; i++)
      coef[i][galb] += coef[i][gala];
    for(int i = 0; i < n; i++)
      coef[galb][i] += coef[gala][i];
    mult[gala] = galb;
  }
}

void initialize(int n_) {
  n = n_;
  Dsu::init();
}

int hasEdge(int u, int v) {
  u = Dsu::jump(u);
  v = Dsu::jump(v);
  coef[u][v]++;
  coef[v][u]++;
  if(Dsu::sz[u] * Dsu::sz[v] == coef[u][v]) {
    Dsu::unite(u, v);
    return 1;
  } else
    return 0;
}

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