| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1146314 | aarb_.tomatexd | Game (IOI14_game) | C++20 | 0 ms | 0 KiB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
// --- Parámetros Globales y estructuras --- //
// Suponemos que n no excede de MAX_N.
static const int MAX_N = 1100;
int nCities;
// Estructura de Union-Find (Disjoint Set)
int parent[MAX_N];
int compSize[MAX_N];
// Para cada representante, guardamos la lista de vértices en ese componente.
vector<int> compVertices[MAX_N];
// Matriz global para marcar que la pregunta sobre (u,v) ya se hizo.
// Usamos la convención: para u < v, asked[u][v] es true si la consulta (u,v) se hizo.
bool asked[MAX_N][MAX_N];
// Función find con compresión de caminos.
int findp(int a) {
if (parent[a] == a) return a;
return parent[a] = findp(parent[a]);
}
// Función de unión: une los componentes de a y b (se unen por tamaño).
void unionComponents(int a, int b) {
a = findp(a), b = findp(b);
if(a == b) return;
if(compSize[a] < compSize[b]) swap(a, b);
parent[b] = a;
compSize[a] += compSize[b];
// Fusionar la lista de vértices: agregamos los vértices de b a a.
for (int v : compVertices[b]) {
compVertices[a].push_back(v);
}
compVertices[b].clear();
}
// Dada dos componentes (identificadas por sus representantes),
// cuenta cuántos pares (x,y) con x en el primer y y en el segundo ya han sido preguntados.
int countAskedBetween(int compA, int compB) {
int cnt = 0;
for (int u : compVertices[compA]) {
for (int v : compVertices[compB]) {
int a = min(u, v), b = max(u, v);
if (asked[a][b])
cnt++;
}
}
return cnt;
}
// --- Interfaz requerida: las dos funciones --- //
extern "C" {
// Se llama al inicio de cada juego.
void initialize(int n) {
nCities = n;
// Inicializar union-find y las listas de componentes.
for (int i = 0; i < n; i++) {
parent[i] = i;
compSize[i] = 1;
compVertices[i].clear();
compVertices[i].push_back(i);
}
// Inicializar la matriz 'asked'. Solo consideramos u<v.
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
asked[i][j] = false;
}
}
}
// Se invoca para cada pregunta: ¿existe vuelo directo entre u y v?
// Debe contestar inmediatamente 1 (sí) o 0 (no).
int hasEdge(int u, int v) {
// Asegurarse de trabajar con u < v para la matriz.
if (u > v) swap(u, v);
// Registrar que la consulta (u,v) se hizo.
asked[u][v] = true;
// Obtener los representantes (componentes) de u y v.
int ru = findp(u), rv = findp(v);
if (ru == rv) {
// Ya están conectados mediante respuestas "yes" anteriores.
// Responder "no" es seguro.
return 0;
}
// Si pertenecen a componentes distintas:
// El número total de pares (x,y) con x en componente ru y y en rv es:
int total_possible = compSize[ru] * compSize[rv];
// Contamos cuántos de esos pares ya se han preguntado (sin importar la respuesta, pues
// siempre se registran cuando se hacen).
int cnt = countAskedBetween(ru, rv);
// Si esta consulta es la ÚLTIMA posible entre estas dos componentes, entonces:
// cnt == total_possible - 1.
// En ese caso, si contestáramos "no", entonces en cualquier completación las dos
// componentes quedarían desconectadas; para preservar la ambigüedad (y ganar el juego)
// debemos contestar "yes" y unirlas.
if (cnt == total_possible - 1) {
unionComponents(ru, rv);
return 1;
}
else {
// Si aún hay otras posibilidades, contestamos "no".
return 0;
}
}
} // extern "C"