Submission #1105042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105042		LucaLucaM	Game (IOI14_game)	C++17	42 / 100	1059 ms	12880 KiB

game

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

const int NMAX = 1000;

std::vector<int> g[NMAX];
std::set<int> unused[NMAX];
bool vis[NMAX];

int n;

void initialize(int N) {
  n = N;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      unused[i].insert(j);
      unused[j].insert(i);
    }
  }
}

void dfs(int u) {
  vis[u] = true;
  for (const auto &v : g[u]) {
    if (!vis[v]) {
      dfs(v);
    }
  }
  for (const auto &v : unused[u]) {
    if (!vis[v]) {
      dfs(v);
    }
  }
}
 
bool conex() {
  for (int i = 0; i < n; i++) {
    vis[i] = false;
  }
  dfs(0);
  for (int i = 0; i < n; i++) {
    if (!vis[i]) {
      return false;
    }
  }
  return true;
}

int hasEdge(int u, int v) {
  unused[u].erase(v);
  unused[v].erase(u);
  if (!conex()) {
    g[u].push_back(v);
    g[v].push_back(u);
    return 1;
  }
  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

*/

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