Submission #1146315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146315		aarb_.tomatexd	Game (IOI14_game)	C++20	0 / 100	0 ms	324 KiB

game

#include <bits/stdc++.h>
using namespace std;

// Máximo número de ciudades (ajusta este valor según las restricciones del problema)
static const int MAX_N = 1100;
int nCities;

// Estructura Union-Find (Disjoint Set) para mantener la conectividad
int parent[MAX_N];
int compSize[MAX_N];
// Para cada representante, mantenemos la lista de vértices (ciudades) en esa componente.
vector<int> compVertices[MAX_N];

// Matriz global para marcar que la pregunta (u,v) ya se hizo.
// Se utiliza la convención: para u < v, asked[u][v] == true indica que la consulta se realizó.
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 para unir dos componentes (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];
    // Fusionamos las listas de vértices.
    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 componente y y en el segundo ya han sido consultados.
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;
}

// Se llama al inicio de cada juego.
void initialize(int n) {
    nCities = n;
    // Inicializamos 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);
    }
    // Inicializamos la matriz 'asked'. Sólo 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 un vuelo directo entre u y v?".
// Debe responder inmediatamente 1 (sí) o 0 (no).
int hasEdge(int u, int v) {
    // Asegurarse de trabajar con u < v para la matriz 'asked'
    if (u > v) swap(u, v);
    
    // Registrar que se realizó la consulta (u, v).
    asked[u][v] = true;
    
    // Obtenemos los representantes (componentes) de u y v.
    int ru = findp(u), rv = findp(v);
    
    if (ru == rv) {
        // Ya están conectados a través de respuestas "yes" anteriores, por lo que se responde "no".
        return 0;
    }
    
    // Si pertenecen a componentes diferentes:
    // El número total de pares entre las dos componentes es:
    int total_possible = compSize[ru] * compSize[rv];
    
    // Contamos cuántos de esos pares ya se han consultado.
    int cnt = countAskedBetween(ru, rv);
    
    // Si esta consulta es la ÚLTIMA posibilidad para conectar estas dos componentes
    // (es decir, se han consultado total_possible - 1 de los pares), debemos contestar "yes"
    // para no dejar revelada la conectividad (y así, Jian-Jia gana el juego).
    if (cnt == total_possible - 1) {
        unionComponents(ru, rv);
        return 1;
    }
    else {
        // En otro caso, contestamos "no".
        return 0;
    }
}

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