제출 #1105061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1105061		LucaLucaM	게임 (IOI14_game)	C++17	0 / 100	1 ms	508 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(p[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