Submission #1010153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010153		SonicML	Game (IOI14_game)	C++14	100 / 100	249 ms	26476 KiB

game

#include <iostream>
#include <vector>
#include "game.h"

using namespace std;

int n;

int const NMAX = 1500;
int root[1 + NMAX];
int treeSize[1 + NMAX];
int unchecked[1 + NMAX][1 + NMAX];

int findRoot(int node) {
  if(root[node] == node) {
    return node;
  }
  root[node] = findRoot(root[node]);
  return root[node];
}

void combineNode(int a, int b) {
  int rootA = findRoot(a), rootB = findRoot(b);
  if(rootA != rootB) {
    if(treeSize[rootA] < treeSize[rootB]) {
      treeSize[rootB] += treeSize[rootA];
      root[rootA] = rootB;
      for(int i = 1;i <= n;i++) {
        unchecked[rootB][i] += unchecked[rootA][i];
        unchecked[i][rootB] += unchecked[i][rootA];
        unchecked[rootA][i] = unchecked[i][rootA] = 0;
      }
    }else {
      treeSize[rootA] += treeSize[rootB];
      root[rootB] = rootA;
      for(int i = 1;i <= n;i++) {
        unchecked[rootA][i] += unchecked[rootB][i];
        unchecked[i][rootA] += unchecked[i][rootB];
        unchecked[rootB][i] = unchecked[i][rootB] = 0;
      }
    }
  }
  return;
}

void initialize(int m) {
  n = m;
  for(int i = 1;i <= n;i++) {
    root[i] = i;
    treeSize[i] = 1;
    for(int j = 1;j <= n;j++) {
      if(i != j) {
        unchecked[i][j] = 1;
      }
    }
  }
  return;
}

bool isLastEdge(int a, int b) {
  int rootA = findRoot(a), rootB = findRoot(b);
  //cerr << rootA << ' ' << rootB << ":\n";
  if(rootA != rootB) {
    unchecked[rootA][rootB]--;
    unchecked[rootB][rootA]--;
    //cerr << "  " << unchecked[rootA][rootB] << '\n';
    if(unchecked[rootA][rootB] == 0) {
      return true;
    }
  }
  return false;
}

int hasEdge(int a, int b) {
  //cerr << "what the heck!?";
  a++;
  b++;
  if(isLastEdge(a, b)) {
    combineNode(a, b);
    return 1;
  }
  return 0;
}

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