Aoi y Bitaro son espías de la Oficina Nacional de Información del país JOI. Su misión esta vez es realizar una investigación encubierta en el país IOI. Bitaro se infiltra en el país IOI, mientras Aoi le da instrucciones desde el país JOI.

Antes de la infiltración, Aoi y Bitaro consiguieron un mapa del país IOI. El país IOI tiene $N$ ciudades, numeradas de $0$ a $N-1$. Además, hay $M$ carreteras, numeradas de $0$ a $M-1$. La carretera $i$ ($0\le i\le M-1$) conecta las ciudades $A_i$ y $B_i$ en ambos sentidos y tiene longitud $C_i$. Es posible viajar entre cualquier par de ciudades recorriendo algunas carreteras. Bitaro se desplaza entre las ciudades del país IOI por estas carreteras.

Además, hay $Q$ planes de investigación. El plan $j$ ($0\le j\le Q-1$) consiste en investigar la ciudad $T_j$ del país IOI.

Toda la información anterior se proporcionó inicialmente tanto a Aoi como a Bitaro. Después, Bitaro comenzó su infiltración en el país IOI.

Bitaro logró esquivar a numerosos perseguidores, derrotó a asesinos y finalmente consiguió infiltrarse en la ciudad $0$ del país IOI. Sin embargo, debido a la extrema dificultad de la operación, perdió parte de la información sobre el país IOI. En concreto, perdió la información sobre las longitudes de $K$ carreteras, las carreteras $X_0,X_1,\ldots,X_{K-1}$. Es decir, Bitaro ya no conoce los valores $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Aunque Bitaro perdió esta información, Aoi aún la conserva.

Bitaro informó inmediatamente a Aoi de qué longitudes de carreteras había perdido la información.

Para cumplir la misión, Bitaro quiere conocer un camino más corto desde la ciudad $0$ hasta cada una de las ciudades objetivo de los $Q$ planes de investigación.

Aoi enviará a Bitaro una cadena cuyos caracteres sean 0 o 1 para ayudarlo. Debido al riesgo de interceptación, Aoi quiere minimizar el contenido enviado a Bitaro.

Escribe un programa que implemente la estrategia de Aoi para enviar una cadena a Bitaro, dada la información sobre el país IOI, los planes de investigación y las carreteras cuya información perdió Bitaro. Escribe también un programa que implemente la estrategia de Bitaro para encontrar los caminos más cortos, dada la información que posee y la cadena enviada por Aoi.

Detalles de implementación

Debes entregar 2 archivos.

El primer archivo es Aoi.cpp. Este archivo debe implementar la estrategia de Aoi mediante las siguientes funciones. El programa debe incluir Aoi.h usando la directiva del preprocesador #include.

• std::string aoi(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X)

  Esta función se llama una sola vez por cada caso de prueba.

  • El parámetro N es el número de ciudades del reino IOI, $N$.
  • El parámetro M es el número de carreteras del reino IOI, $M$.
  • El parámetro Q es el número de planes de investigación, $Q$.
  • El parámetro K es el número de carreteras cuya información de longitud perdió Bitaro, denotado por $K$.
  • Los parámetros A, B, C son arreglos de longitud $M$. Indican que la carretera $i$ ($0\le i\le M-1$) conecta las ciudades A[i] y B[i] en ambos sentidos y tiene longitud C[i].
  • El parámetro T es un arreglo de longitud $Q$. Indica que el plan $j$ ($0\le j\le Q-1$) consiste en investigar la ciudad T[j].
  • El parámetro X es un arreglo de longitud $K$. Indica que Bitaro perdió la información sobre las longitudes de las carreteras X[0], X[1], …, X[K-1].
  • El valor de retorno es la cadena $s$ que Aoi envía a Bitaro.
  • Cada carácter de la cadena $s$ debe ser 0 o 1. Si no se cumple esta condición, tu programa recibirá Wrong Answer [1].
  • La longitud de la cadena $s$ debe ser como máximo $12\,000$. Si no se cumple esta condición, tu programa recibirá Wrong Answer [2].

El segundo archivo es Bitaro.cpp. Este archivo debe implementar la estrategia de Bitaro mediante las siguientes funciones. El programa debe incluir Bitaro.h usando la directiva del preprocesador #include.

• void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X, std::string s)

  Esta función se llama una sola vez después de llamar a aoi.

  • El parámetro N es el número de ciudades del reino IOI, $N$.
  • El parámetro M es el número de carreteras del reino IOI, $M$.
  • El parámetro Q es el número de planes de investigación, $Q$.
  • El parámetro K es el número de carreteras cuya información de longitud perdió Bitaro, denotado por $K$.
  • Los parámetros A, B, C son arreglos de longitud $M$. Indican que la carretera $i$ ($0\le i\le M-1$) conecta las ciudades A[i] y B[i] en ambos sentidos y tiene longitud C[i].
  • El parámetro T es un arreglo de longitud $Q$. Indica que el plan $j$ ($0\le j\le Q-1$) consiste en investigar la ciudad T[j].
  • El parámetro X es un arreglo de longitud $K$. Indica que Bitaro perdió la información sobre las longitudes de las carreteras X[0], X[1], …, X[K-1].
  • El argumento s es una cadena cuyos caracteres son 0 o 1, que representa la cadena enviada por Aoi a Bitaro.

Dentro de Bitaro.cpp, tu programa puede llamar a la siguiente función.

• void answer(const std::vector<int> &e)

  En la llamada número $j+1$ ($0\le j\le Q-1$) a esta función, debes responder con el camino más corto desde la ciudad $0$ hasta la ciudad $T_j$, objetivo del plan de investigación $j$.

  • El parámetro e es un arreglo que representa el camino más corto desde la ciudad $0$ hasta la ciudad $T_j$.
  • Sea $n$ la longitud del arreglo e. Los elementos e[0], e[1], …, e[n-1] son los índices de las carreteras del camino más corto desde la ciudad $0$ hasta la ciudad $T_j$, en el orden en que se recorren.
  • Si existen varios caminos más cortos, puedes elegir cualquiera como respuesta.
  • Cada elemento del parámetro e debe estar entre $0$ y $M-1$. Si no se cumple esta condición, tu programa recibirá Wrong Answer [3].

  • La secuencia de carreteras indicada por el argumento e debe formar un camino desde la ciudad $0$ hasta la ciudad $T_j$. Más formalmente, debe cumplir las siguientes condiciones.

    Existe una secuencia de números $u_0,u_1,\ldots,u_n$ tal que:

    • $u_0=0$.
    • $u_n=T_j$.
    • La carretera e[k] (donde $0\le k\le n-1$) conecta las ciudades $u_k$ y $u_{k+1}$.

    Si no se cumplen estas condiciones, tu programa recibirá Wrong Answer [4].

  • Si la secuencia de carreteras indicada por el argumento e no es un camino más corto desde la ciudad $0$ hasta la ciudad $T_j$ entre todos los caminos que empiezan en la ciudad $0$ y terminan en la ciudad $T_j$, tu programa recibirá Wrong Answer [5]. Aquí, la longitud de un camino se define como la suma de las longitudes de las carreteras utilizadas.

  • La función answer debe llamarse exactamente $Q$ veces. Si el número de llamadas a answer no es igual a $Q$ cuando termina la ejecución de bitaro, tu programa recibirá Wrong Answer [6].

Avisos importantes

• Tu programa puede implementar otras funciones para uso interno o utilizar variables globales. Los archivos entregados se compilarán junto con el evaluador y formarán un solo archivo ejecutable. Todas las variables globales y funciones internas deben declararse en un espacio de nombres sin nombre para evitar conflictos con otros archivos. Durante la evaluación, se ejecutará en dos procesos, uno de Aoi y otro de Bitaro. Los procesos de Aoi y Bitaro no pueden compartir variables globales.
• Tu programa no debe utilizar la entrada estándar ni la salida estándar. Tampoco debe comunicarse con otros archivos por ningún medio. Sin embargo, puede escribir información de depuración en la salida de error estándar.

Compilación y pruebas

Puedes descargar de la página de la competición un archivo comprimido que contiene el evaluador de ejemplo para probar tu programa. También contiene un archivo de código fuente de ejemplo de tu programa.

El evaluador de ejemplo es grader.cpp. Para probar tu programa, coloca grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h en el mismo directorio y ejecuta el siguiente comando para compilar. Como alternativa, puedes ejecutar compile.sh, incluido en el archivo comprimido.

g++ -std=gnu++20 -O2 -o grader grader.cpp Aoi.cpp Bitaro.cpp

Si la compilación tiene éxito, se genera el archivo ejecutable grader.

Ten en cuenta que el evaluador real es distinto del evaluador de ejemplo. El evaluador de ejemplo se ejecuta como un solo proceso, que lee los datos de la entrada estándar y escribe los resultados en la salida estándar y en la salida de error estándar.

Entrada del evaluador de ejemplo

El evaluador de ejemplo lee los siguientes datos de la entrada estándar.

$$ \begin{gathered} N\ M\\ A_0\ B_0\ C_0\\ A_1\ B_1\ C_1\\ \vdots\\ A_{M-1}\ B_{M-1}\ C_{M-1}\\ Q\\ T_0\ T_1\ \ldots\ T_{Q-1}\\ K\\ X_0\ X_1\ \ldots\ X_{K-1} \end{gathered} $$

Salida del evaluador de ejemplo

El evaluador de ejemplo escribe la siguiente información en la salida estándar y en la salida de error estándar (las comillas se usan para mayor claridad).

• Si tu programa recibe Wrong Answer [1], [2], [3], [4] o [6], el evaluador de ejemplo escribe su tipo como Wrong Answer [1] en la salida de error estándar. No se escribe nada en la salida estándar.
• En caso contrario, la longitud de la cadena $s$ devuelta por aoi se escribe en la salida de error estándar con el formato Accepted: 2024. Además, la longitud del camino de la llamada número $j+1$ ($0\le j\le Q-1$) a answer se escribe en la línea número $j+1$ de la salida estándar. El evaluador de ejemplo no comprueba si el camino es el más corto.

Si tu programa cumple las condiciones de varios tipos de Wrong Answer, el evaluador de ejemplo solo informa de uno.

Restricciones

Todos los datos de entrada cumplen las siguientes condiciones:

• $2\le N\le 10\,000$.
• $1\le M\le 20\,000$.
• $1\le Q\le 16$.
• $1\le K\le 300$.
• $0\le A_i<B_i\le N-1$ ($0\le i\le M-1$).
• $(A_i,B_i)\ne(A_j,B_j)$ ($0\le i<j\le M-1$).
• $1\le C_i\le 10^{12}$ ($0\le i\le M-1$).
• $1\le T_j\le N-1$ ($0\le j\le Q-1$).
• $T_j\ne T_k$ ($0\le j<k\le Q-1$).
• $0\le X_k\le M-1$ ($0\le k\le K-1$).
• $X_k\ne X_l$ ($0\le k<l\le K-1$).
• Es posible viajar de cualquier ciudad a cualquier otra recorriendo algunas carreteras.
• Todos los valores de entrada son enteros.

Subtareas

Si tu programa recibe cualquier tipo de Wrong Answer [1]–[6] (consulta Detalles de implementación) o cualquier error de ejecución (TLE (tiempo límite excedido), MLE (memoria límite excedida), finalización anormal, etc.) en cualquiera de los casos de prueba, tu puntuación es de 0 puntos.

En caso contrario, la puntuación se basa en la longitud máxima de la cadena $s$ devuelta por aoi en todos los casos de prueba de este problema, denotada por $L$.

• Si $1561\le L\le 12\,000$, la puntuación es de $\left\lfloor\frac{100\,000}{L-560}\right\rfloor$ puntos.
• Si $0\le L\le 1560$, la puntuación es de 100 puntos.

Aquí, $\lfloor x\rfloor$ representa el mayor entero que no es mayor que $x$.

Ejemplo de comunicación

A continuación se muestra una entrada de ejemplo para el evaluador de ejemplo y las llamadas a funciones correspondientes.

Entrada 1

3 3
1 2 1
0 2 2
0 1 3
2
2 1
2
0 1

Llamadas a funciones de ejemplo

El camino más corto desde la ciudad $0$ hasta la ciudad $1$ se obtiene recorriendo las carreteras $1$ y $0$ en ese orden, o simplemente recorriendo la carretera $2$. Por lo tanto, en la segunda llamada a answer de este ejemplo también es válido llamar a answer([2]).

El archivo descargable desde la página de la competición sample-01-in.txt corresponde a la entrada del ejemplo 1.

Los archivos sample-01-in.txt y sample-02-in.txt incluidos entre los archivos descargables de la página de la competición pueden utilizarse como entrada para el evaluador de ejemplo.