Submission #1130544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130544		Ak_16	Game (IOI14_game)	C++17	100 / 100	323 ms	16492 KiB

game

#include <iostream>
using namespace std;
int bruh;


int par[2000];
int siz[2000];

int cnt[1600][1600];

int fin(int x){
  if(par[x]==x){return x;}
  else {return fin(par[x]);}
}

void unite(int x, int y){
  int xr = fin(x);
  int yr = fin(y);
  if(siz[xr]<siz[yr]){swap(xr, yr);}
  par[yr] = xr;
  siz[xr] += siz[yr];
}

void initialize(int du){
  bruh = du;
  for(int i=1; i<=du; i++){
    par[i] = i; siz[i] = 1;
  }
  for(int i=1; i<=du; i++){
    for(int j=1; j<=du; j++){
      cnt[i][j] = 0;
    }
  }
}

int hasEdge(int u, int v){
  u++; v++;
  int n1 = fin(u);
  int n2 = fin(v);
  int n3 = siz[n1];
  int n4 = siz[n2];
  
  if(cnt[n1][n2] == n3 * n4 - 1){
    unite(n1, n2);
    cnt[n1][n2]++;
    cnt[n2][n1]++;
    if(n3<n4){
      swap(n1, n2);
    }
    for(int i=1; i<=bruh; i++){
      cnt[i][n1] += cnt[i][n2];
      cnt[n1][i] += cnt[n2][i];
    }
    return 1;
  }
  else {
    cnt[n1][n2]++;
    cnt[n2][n1]++;
    return 0;
  }
}

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