Aoi et Bitaro sont des espions du Bureau national du renseignement du pays JOI. Leur mission consiste cette fois à mener une enquête clandestine dans le pays IOI. Bitaro s'infiltre dans le pays IOI tandis qu'Aoi lui donne des instructions depuis le pays JOI.

Avant l'infiltration, Aoi et Bitaro ont obtenu une carte du pays IOI. Celui-ci compte $N$ villes, numérotées de $0$ à $N-1$, et $M$ routes, numérotées de $0$ à $M-1$. La route $i$ ($0\le i\le M-1$) relie les villes $A_i$ et $B_i$ dans les deux sens et a une longueur de $C_i$. Toute paire de villes est reliée par un parcours empruntant des routes. Bitaro se déplace entre les villes du pays IOI par ces routes.

Il existe également $Q$ plans d'enquête. Le plan $j$ ($0\le j\le Q-1$) consiste à enquêter dans la ville $T_j$ du pays IOI.

Toutes ces informations ont d'abord été données à Aoi et à Bitaro. Bitaro a ensuite commencé son infiltration dans le pays IOI.

Bitaro a réussi à échapper à de nombreux poursuivants, à vaincre des assassins et enfin à s'infiltrer dans la ville $0$ du pays IOI. Cependant, l'extrême difficulté de l'opération lui a fait perdre certaines informations sur ce pays. Plus précisément, il a perdu les longueurs de $K$ routes : $X_0,X_1,\ldots,X_{K-1}$. Autrement dit, il ne connaît plus les valeurs $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Aoi, elle, possède toujours ces informations.

Bitaro a immédiatement indiqué à Aoi quelles longueurs de routes il avait perdues.

Pour accomplir sa mission, Bitaro veut connaître un plus court chemin de la ville $0$ à chacune des villes ciblées par les $Q$ plans d'enquête.

Aoi lui enverra une chaîne dont chaque caractère est 0 ou 1 pour l'aider. En raison du risque d'interception, elle souhaite minimiser la quantité d'informations envoyée à Bitaro.

Écrivez un programme qui implémente la stratégie d'Aoi pour envoyer une chaîne à Bitaro, à partir des informations sur le pays IOI, les plans d'enquête et les routes dont Bitaro a perdu la longueur. Écrivez aussi un programme qui implémente la stratégie de Bitaro pour trouver les plus courts chemins à partir des informations qu'il possède et de la chaîne envoyée par Aoi.

Détails d'implémentation

Vous devez soumettre 2 fichiers.

Le premier fichier est Aoi.cpp. Il implémente la stratégie d'Aoi et doit fournir les fonctions suivantes. Le programme doit inclure Aoi.h avec la directive de préprocesseur #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)

Cette fonction est appelée une seule fois par cas de test.

• Le paramètre N est le nombre $N$ de villes du Royaume IOI.
• Le paramètre M est le nombre $M$ de routes du Royaume IOI.
• Le paramètre Q est le nombre $Q$ de plans d'enquête.
• Le paramètre K est le nombre $K$ de routes dont Bitaro a perdu la longueur.
• Les paramètres A, B, C sont des tableaux de longueur $M$. Ils indiquent que la route $i$ ($0\le i\le M-1$) relie les villes A[i] et B[i] dans les deux sens et a une longueur de C[i].
• Le paramètre T est un tableau de longueur $Q$. Il indique que le plan $j$ ($0\le j\le Q-1$) consiste à enquêter dans la ville T[j].
• Le paramètre X est un tableau de longueur $K$. Il indique que Bitaro a perdu les longueurs des routes X[0], X[1], ..., X[K-1].
• La valeur renvoyée est la chaîne $s$ envoyée par Aoi à Bitaro.
• Chaque caractère de $s$ doit être 0 ou 1. Sinon, votre programme reçoit le verdict Réponse incorrecte [1].
• La longueur de $s$ doit être au plus $12\,000$. Sinon, votre programme reçoit le verdict Réponse incorrecte [2].

Le second fichier est Bitaro.cpp. Il implémente la stratégie de Bitaro et doit fournir les fonctions suivantes. Le programme doit inclure Bitaro.h avec la directive de préprocesseur #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)

Cette fonction est appelée une seule fois, après l'appel à aoi.

• Le paramètre N est le nombre $N$ de villes du Royaume IOI.
• Le paramètre M est le nombre $M$ de routes du Royaume IOI.
• Le paramètre Q est le nombre $Q$ de plans d'enquête.
• Le paramètre K est le nombre $K$ de routes dont Bitaro a perdu la longueur.
• Les paramètres A, B, C sont des tableaux de longueur $M$. Ils indiquent que la route $i$ ($0\le i\le M-1$) relie les villes A[i] et B[i] dans les deux sens et a une longueur de C[i].
• Le paramètre T est un tableau de longueur $Q$. Il indique que le plan $j$ ($0\le j\le Q-1$) consiste à enquêter dans la ville T[j].
• Le paramètre X est un tableau de longueur $K$. Il indique que Bitaro a perdu les longueurs des routes X[0], X[1], ..., X[K-1].
• L'argument s est une chaîne dont chaque caractère est 0 ou 1, représentant la chaîne envoyée par Aoi à Bitaro.

Dans Bitaro.cpp, votre programme peut appeler la fonction suivante.

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

Lors du $j+1$-ième appel ($0\le j\le Q-1$), vous devez indiquer le plus court chemin de la ville $0$ à la ville $T_j$, cible du plan d'enquête $j$.

• Le paramètre e est un tableau représentant le plus court chemin de la ville $0$ à la ville $T_j$.
• Soit $n$ la longueur de e. Les éléments e[0], e[1], ..., e[n-1] sont les indices des routes du plus court chemin de la ville $0$ à la ville $T_j$, dans l'ordre de parcours.
• S'il existe plusieurs plus courts chemins, vous pouvez en choisir n'importe lequel.
• Chaque élément de e doit être compris entre $0$ et $M-1$. Sinon, votre programme reçoit le verdict Réponse incorrecte [3].

• La suite de routes indiquée par e doit former un chemin de la ville $0$ à la ville $T_j$. Plus formellement, elle doit satisfaire les conditions suivantes : il existe une suite de nombres $u_0,u_1,\ldots,u_n$ telle que

  • $u_0=0$.
  • $u_n=T_j$.
  • La route e[k] ($0\le k\le n-1$) relie les villes $u_k$ et $u_{k+1}$.

Si ces conditions ne sont pas satisfaites, votre programme reçoit le verdict Réponse incorrecte [4].

• Si la suite de routes indiquée par e n'est pas un plus court chemin parmi tous les chemins partant de la ville $0$ et se terminant à la ville $T_j$, votre programme reçoit le verdict Réponse incorrecte [5]. La longueur d'un chemin est la somme des longueurs des routes empruntées.
• La fonction answer doit être appelée exactement $Q$ fois. Si le nombre d'appels à answer n'est pas égal à $Q$ à la fin de l'exécution de bitaro, votre programme reçoit le verdict Réponse incorrecte [6].

Remarques importantes

• Votre programme peut implémenter d'autres fonctions internes ou utiliser des variables globales. Les fichiers soumis sont compilés avec l'évaluateur pour former un seul exécutable. Toutes les variables globales et fonctions internes doivent être déclarées dans un espace de noms anonyme pour éviter les conflits avec les autres fichiers. Lors de l'évaluation, deux processus, celui d'Aoi et celui de Bitaro, sont exécutés. Ils ne peuvent pas partager de variables globales.
• Votre programme ne doit utiliser ni l'entrée standard ni la sortie standard. Il ne doit communiquer avec d'autres fichiers par aucun moyen. Il peut toutefois écrire des informations de débogage sur la sortie d'erreur standard.

Compilation et essais

Vous pouvez télécharger sur la page du concours une archive contenant un évaluateur d'exemple pour tester votre programme. L'archive contient aussi un exemple de fichier source pour votre programme.

L'évaluateur d'exemple est le fichier grader.cpp. Pour tester votre programme, placez grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h et Bitaro.h dans le même répertoire, puis exécutez la commande suivante pour compiler les programmes. Vous pouvez aussi exécuter compile.sh, fourni dans l'archive.

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

Si la compilation réussit, l'exécutable grader est créé.

L'évaluateur réel diffère de l'évaluateur d'exemple. Ce dernier s'exécute en un seul processus, lit les données sur l'entrée standard et écrit les résultats sur la sortie standard et la sortie d'erreur standard.

Entrée de l'évaluateur d'exemple

L'évaluateur d'exemple lit les données suivantes sur l'entrée standard.

$$ \begin{array}{l} 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{array} $$

Sortie de l'évaluateur d'exemple

L'évaluateur d'exemple écrit les informations suivantes sur la sortie standard et la sortie d'erreur standard (les guillemets sont donnés pour plus de clarté).

• Si votre programme reçoit l'un des verdicts Réponse incorrecte [1], [2], [3], [4] ou [6], l'évaluateur d'exemple écrit son type, par exemple Wrong Answer [1], sur la sortie d'erreur standard. Rien n'est écrit sur la sortie standard.
• Sinon, la longueur de la chaîne $s$ renvoyée par aoi est écrite sur la sortie d'erreur standard au format Accepted: 2024. De plus, la longueur du chemin indiqué au $j+1$-ième appel ($0\le j\le Q-1$) de answer est écrite à la ligne $j+1$ de la sortie standard. L'évaluateur d'exemple ne vérifie pas que le chemin est le plus court.

Si votre programme satisfait les conditions de plusieurs types de réponse incorrecte, l'évaluateur d'exemple n'en signale qu'un seul.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes :

• $2\le N\le10\,000$.
• $1\le M\le20\,000$.
• $1\le Q\le16$.
• $1\le K\le300$.
• $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\le10^{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$).
• Vous pouvez vous rendre de n'importe quelle ville à n'importe quelle autre en empruntant des routes.
• Toutes les valeurs d'entrée sont des entiers.

Sous-tâches

Si votre programme reçoit l'un des verdicts « Réponse incorrecte [1]–[6] » (voir « Détails d'implémentation ») ou une erreur d'exécution quelconque (TLE : dépassement du temps limite, MLE : dépassement de la mémoire limite, arrêt anormal, etc.) dans n'importe quel cas de test, votre score est de 0 point.

Sinon, l'évaluation repose sur la longueur maximale $L$ de la chaîne $s$ renvoyée par la fonction aoi, sur l'ensemble des cas de test de cette tâche.

• Si $1561\le L\le12\,000$, le score est de $\left\lfloor\frac{100\,000}{L-560}\right\rfloor$ points.
• Si $0\le L\le1560$, le score est de 100 points.

Ici, $\lfloor x\rfloor$ désigne le plus grand entier inférieur ou égal à $x$.

Exemple d'interaction

Voici une entrée d'exemple pour l'évaluateur d'exemple et les appels de fonctions correspondants.

Entrée 1

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

Exemples d'appels de fonctions

Le plus court chemin de la ville $0$ à la ville $1$ peut emprunter les routes $1$ puis $0$, ou simplement la route $2$. Il est donc également acceptable d'appeler answer([2]) lors du deuxième appel à answer de cet exemple.

Le fichier sample-01-in.txt, téléchargeable sur le site du concours, correspond à l'entrée d'exemple 1.

Les fichiers sample-01-in.txt et sample-02-in.txt, disponibles au téléchargement sur le site du concours, peuvent servir d'entrée à l'évaluateur d'exemple.