Submission #1146313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146313		aarb_.tomatexd	Game (IOI14_game)	C++20	Compilation error	0 ms	0 KiB

game

#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"

Compilation message (stderr)

/usr/bin/ld: /tmp/cctqzuum.o: in function `main':
grader.cpp:(.text.startup+0x2c): undefined reference to `initialize(int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x94): undefined reference to `hasEdge(int, int)'
collect2: error: ld returned 1 exit status