Submission #1105060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105060		LucaLucaM	Game (IOI14_game)	C++17	0 / 100	241 ms	262144 KiB

game

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

const int NMAX = 1000;

int n;
int p[NMAX];
int canAdd[NMAX];

int root(int u) {
  return p[u] == u? u : p[u] = root(u);
}
void join(int u, int v) {
  u = root(u);
  v = root(v);
  p[u] = v;
  canAdd[v] += canAdd[u];
  canAdd[v] -= 2; // (u, v) nu il mai numar nici din partea lui u, nici din partea lui v
}

void initialize(int N) {
  n = N;
  for (int i = 0; i < n; i++) {
    canAdd[i] = n - 1;
    p[i] = i;
  }
}

int hasEdge(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) {
    return 0;
  }
  if (canAdd[u] == 1 || canAdd[v] == 1) {
    join(u, v);
    return 1;
  }
  canAdd[u]--;
  canAdd[v]--;
  return 0;
}

/*

strategie: 
fie E muchiile pe care le-am a daugat deja si E' muchiile pe care inca nu le am ales

daca E U E' NU formeaza spanning tree => am pierdut
fie E'' = E' \ {(u, v)} unde (u, v) e muchia curenta de la query
daca E'' U E imi da spanning tree => nu pun (u, v) in E
altfel pun (u, v) in E

asta sa fie oare singuru algoritm corect?
cred ca DA

deci trebuie doar sa vad cum optimizez

*/

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