Submission #117447

#	Time	Username	Problem	Language	Result	Execution time	Memory
117447		dragonslayerit	Game (IOI14_game)	C++14	100 / 100	454 ms	20560 KiB

game

#include "game.h"
#include <cassert>
#include <cstdio>

int conn[1505][1505];
int component[1505];

int N;

void initialize(int n) {
  N=n;
  for(int i=0;i<n;i++){
    component[i]=i;
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      conn[i][j]=(i!=j);
    }
  }
}

void connect(int a,int b){
  for(int i=0;i<N;i++){
    conn[i][a]+=conn[i][b];
    conn[i][b]=0;
    conn[a][i]+=conn[b][i];
    conn[b][i]=0;
  }
  for(int i=0;i<N;i++){
    if(component[i]==b){
      component[i]=a;
    }
  }
}

int hasEdge(int u, int v) {
  int a=component[u],b=component[v];
  assert(a!=b);
  conn[a][b]--;
  conn[b][a]--;
  if(conn[a][b]==0){
    connect(a,b);
    return 1;
  }
  return 0;
}

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