Aoi und Bitaro sind Spione des nationalen Informationsbüros des Landes JOI. Ihre diesmalige Mission ist eine verdeckte Untersuchung im Land IOI. Bitaro dringt in das Land IOI ein, während Aoi ihm vom Land JOI aus Anweisungen gibt.

Vor dem Eindringen haben Aoi und Bitaro eine Karte des Landes IOI erhalten. Das Land IOI hat $N$ Städte, die von $0$ bis $N-1$ nummeriert sind. Außerdem gibt es $M$ Straßen, die von $0$ bis $M-1$ nummeriert sind. Straße $i$ ($0 \le i \le M-1$) verbindet Stadt $A_i$ und Stadt $B_i$ in beide Richtungen und hat die Länge $C_i$. Zwischen je zwei Städten kann man über einige Straßen reisen. Bitaro bewegt sich über diese Straßen zwischen den Städten des Landes IOI.

Außerdem gibt es $Q$ Untersuchungspläne. Der $j$-te Plan ($0 \le j \le Q-1$) sieht die Untersuchung der Stadt $T_j$ im Land IOI vor.

Alle obigen Informationen wurden zunächst sowohl Aoi als auch Bitaro mitgeteilt. Danach begann Bitaro mit dem Eindringen in das Land IOI.

Bitaro entkam erfolgreich zahlreichen Verfolgern, besiegte Attentäter und konnte schließlich in Stadt $0$ des Landes IOI eindringen. Wegen der äußerst schwierigen Operation verlor Bitaro jedoch einige Informationen über das Land IOI. Genauer gesagt verlor er die Längeninformationen von $K$ Straßen, nämlich den Straßen $X_0,X_1,\ldots,X_{K-1}$. Mit anderen Worten kennt Bitaro die Werte $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$ nicht mehr. Beachte, dass Aoi diese Informationen weiterhin besitzt, obwohl Bitaro sie verloren hat.

Bitaro meldete Aoi sofort, von welchen Straßen er die Längeninformationen verloren hatte.

Um die Mission zu erfüllen, möchte Bitaro einen kürzesten Weg von Stadt $0$ zu jeder Zielstadt der $Q$ Untersuchungspläne kennen.

Aoi wird Bitaro zur Unterstützung eine Zeichenkette senden, deren Zeichen jeweils entweder 0 oder 1 sind. Wegen der Gefahr des Abfangens möchte Aoi den an Bitaro gesendeten Inhalt minimieren.

Schreibe ein Programm, das anhand der Informationen über das Land IOI, die Untersuchungspläne und die Straßen, deren Informationen Bitaro verloren hat, Aois Strategie zum Senden einer Zeichenkette an Bitaro implementiert. Schreibe außerdem ein Programm, das anhand der Bitaro bekannten Informationen und der von Aoi gesendeten Zeichenkette Bitaros Strategie zum Finden der kürzesten Wege implementiert.

Implementierungsdetails

Du musst 2 Dateien einreichen.

Die erste Datei ist Aoi.cpp. Sie soll Aois Strategie implementieren und muss die folgende Funktion implementieren. Das Programm muss Aoi.h mit der Präprozessordirektive #include einbinden.

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)

Diese Funktion wird für jeden Testfall genau einmal aufgerufen.

• Der Parameter $N$ ist die Anzahl $N$ der Städte im Land IOI.
• Der Parameter $M$ ist die Anzahl $M$ der Straßen im Land IOI.
• Der Parameter $Q$ ist die Anzahl $Q$ der Untersuchungspläne.
• Der Parameter $K$ ist die Anzahl der Straßen, deren Längeninformationen Bitaro verloren hat, bezeichnet mit $K$.
• Die Parameter $A,B,C$ sind Arrays der Länge $M$. Sie bedeuten, dass Straße $i$ ($0 \le i \le M-1$) Stadt A[i] und Stadt B[i] in beide Richtungen verbindet und die Länge C[i] hat.
• Der Parameter $T$ ist ein Array der Länge $Q$. Es bedeutet, dass der $j$-te Plan ($0 \le j \le Q-1$) die Untersuchung der Stadt T[j] vorsieht.
• Der Parameter $X$ ist ein Array der Länge $K$. Es gibt an, dass Bitaro die Längeninformationen der Straßen X[0], X[1], ..., X[K-1] verloren hat.
• Der Rückgabewert ist die Zeichenkette $s$, die Aoi an Bitaro sendet.
• Jedes Zeichen der Zeichenkette $s$ muss entweder 0 oder 1 sein. Ist diese Bedingung nicht erfüllt, wird dein Programm mit Wrong Answer [1] bewertet.
• Die Länge der Zeichenkette $s$ darf höchstens $12\,000$ betragen. Ist diese Bedingung nicht erfüllt, wird dein Programm mit Wrong Answer [2] bewertet.

Die zweite Datei ist Bitaro.cpp. Sie soll Bitaros Strategie implementieren und muss die folgende Funktion implementieren. Das Programm muss Bitaro.h mit der Präprozessordirektive #include einbinden.

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)

Diese Funktion wird nach dem Aufruf der Funktion aoi genau einmal aufgerufen.

• Der Parameter $N$ ist die Anzahl $N$ der Städte im Land IOI.
• Der Parameter $M$ ist die Anzahl $M$ der Straßen im Land IOI.
• Der Parameter $Q$ ist die Anzahl $Q$ der Untersuchungspläne.
• Der Parameter $K$ ist die Anzahl der Straßen, deren Längeninformationen Bitaro verloren hat, bezeichnet mit $K$.
• Die Parameter $A,B,C$ sind Arrays der Länge $M$. Sie bedeuten, dass Straße $i$ ($0 \le i \le M-1$) Stadt A[i] und Stadt B[i] in beide Richtungen verbindet und die Länge C[i] hat.
• Der Parameter $T$ ist ein Array der Länge $Q$. Es bedeutet, dass der $j$-te Plan ($0 \le j \le Q-1$) die Untersuchung der Stadt T[j] vorsieht.
• Der Parameter $X$ ist ein Array der Länge $K$. Es gibt an, dass Bitaro die Längeninformationen der Straßen X[0], X[1], ..., X[K-1] verloren hat.
• Das Argument $s$ ist eine Zeichenkette, deren Zeichen jeweils entweder 0 oder 1 sind. Sie stellt die von Aoi an Bitaro gesendete Zeichenkette dar.

In Bitaro.cpp kann dein Programm die folgende Funktion aufrufen.

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

Beim $(j+1)$-ten Aufruf dieser Funktion ($0 \le j \le Q-1$) musst du den kürzesten Weg von Stadt $0$ zu Stadt $T_j$, dem Ziel des $j$-ten Untersuchungsplans, angeben.

• Der Parameter $e$ ist ein Array, das den kürzesten Weg von Stadt $0$ zu Stadt $T_j$ darstellt.
• Sei $n$ die Länge des Arrays $e$. Die Elemente e[0], e[1], ..., e[n-1] sind die Nummern der Straßen auf dem kürzesten Weg von Stadt $0$ zu Stadt $T_j$ in der Reihenfolge, in der sie durchlaufen werden.
• Gibt es mehrere mögliche kürzeste Wege, darf jeder davon als Antwort gewählt werden.
• Jedes Element des Parameters $e$ muss zwischen $0$ und $M-1$ liegen. Ist diese Bedingung nicht erfüllt, wird dein Programm mit Wrong Answer [3] bewertet.

• Die durch das Argument $e$ angegebene Straßenfolge muss einen Weg von Stadt $0$ zu Stadt $T_j$ bilden. Formal muss sie die folgenden Bedingungen erfüllen.

  Es gibt eine Zahlenfolge $u_0,u_1,\ldots,u_n$, sodass:

  • $u_0=0$.
  • $u_n=T_j$.
  • Straße e[k] (mit $0 \le k \le n-1$) verbindet Stadt $u_k$ und Stadt $u_{k+1}$.

  Sind diese Bedingungen nicht erfüllt, wird dein Programm mit Wrong Answer [4] bewertet.

• Ist die durch das Argument $e$ angegebene Straßenfolge unter allen Wegen mit Start in Stadt $0$ und Ende in Stadt $T_j$ kein kürzester Weg, wird dein Programm mit Wrong Answer [5] bewertet. Die Länge eines Weges ist dabei als Summe der Längen der verwendeten Straßen definiert.

• Die Funktion answer muss genau $Q$-mal aufgerufen werden. Ist die Anzahl ihrer Aufrufe am Ende der Ausführung der Funktion bitaro nicht gleich $Q$, wird dein Programm mit Wrong Answer [6] bewertet.

Wichtige Hinweise

• Dein Programm darf weitere Funktionen für die interne Verwendung implementieren oder globale Variablen verwenden. Die eingereichten Dateien werden zusammen mit dem Grader zu einer einzigen ausführbaren Datei kompiliert. Alle globalen Variablen und internen Funktionen sollen in einem unbenannten Namensraum deklariert werden, um Konflikte mit anderen Dateien zu vermeiden. Bei der Bewertung wird das Programm in zwei Prozessen für Aoi und Bitaro ausgeführt. Aois und Bitaros Prozess können keine globalen Variablen gemeinsam nutzen.
• Dein Programm darf die Standardeingabe und Standardausgabe nicht verwenden. Es darf auf keine Weise mit anderen Dateien kommunizieren. Es darf jedoch Informationen zur Fehlersuche auf der Standardfehlerausgabe ausgeben.

Kompilierung und Testausführung

Auf der Wettbewerbswebsite kannst du ein Archiv mit einem Beispielgrader herunterladen, um dein Programm zu testen. Das Archiv enthält auch Beispielquellcode für dein Programm.

Der Beispielgrader ist die Datei grader.cpp. Lege zum Testen deines Programms grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h und Bitaro.h in dasselbe Verzeichnis und führe den folgenden Befehl aus, um deine Programme zu kompilieren. Stattdessen kannst du auch das im Archiv enthaltene compile.sh ausführen.

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

Bei erfolgreicher Kompilierung wird die ausführbare Datei grader erzeugt.

Beachte, dass der tatsächliche Grader vom Beispielgrader verschieden ist. Der Beispielgrader wird als einzelner Prozess ausgeführt, der Eingabedaten von der Standardeingabe liest und die Ergebnisse auf die Standardausgabe und die Standardfehlerausgabe schreibt.

Eingabe des Beispielgraders

Der Beispielgrader liest die folgenden Daten von der Standardeingabe.

N M
A_0 B_0 C_0
A_1 B_1 C_1
...
A_{M-1} B_{M-1} C_{M-1}
Q
T_0 T_1 ... T_{Q-1}
K
X_0 X_1 ... X_{K-1}

Ausgabe des Beispielgraders

Der Beispielgrader gibt die folgenden Informationen auf der Standardausgabe und der Standardfehlerausgabe aus (Anführungszeichen dienen der Verdeutlichung).

• Wird dein Programm mit Wrong Answer [1], [2], [3], [4] oder [6] bewertet, schreibt der Beispielgrader den entsprechenden Typ in einer Form wie Wrong Answer [1] auf die Standardfehlerausgabe. Auf der Standardausgabe wird nichts ausgegeben.
• Andernfalls wird die Länge der von aoi zurückgegebenen Zeichenkette $s$ im Format Accepted: 2024 auf der Standardfehlerausgabe ausgegeben. Außerdem wird die Länge des Weges im $(j+1)$-ten Aufruf ($0 \le j \le Q-1$) der Funktion answer in der $(j+1)$-ten Zeile der Standardausgabe ausgegeben. Der Beispielgrader prüft nicht, ob der Weg ein kürzester Weg ist.

Erfüllt dein Programm die Bedingungen mehrerer Arten von Wrong Answer, meldet der Beispielgrader nur eine davon.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen:

• $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$).
• Von jeder Stadt kann man über einige Straßen zu jeder anderen Stadt reisen.
• Alle Eingabewerte sind ganze Zahlen.

Teilaufgaben

Wird dein Programm in irgendeinem Testfall mit einer beliebigen Art von Wrong Answer [1]–[6] (siehe Implementierungsdetails) bewertet oder tritt ein Laufzeitfehler beliebiger Art auf (TLE (Zeitlimit überschritten), MLE (Speicherlimit überschritten), abnormales Ende usw.), erhältst du 0 Punkte.

Andernfalls richtet sich die Bewertung nach der maximalen Länge der von aoi zurückgegebenen Zeichenkette $s$ über alle Testfälle dieser Aufgabe. Diese Länge wird mit $L$ bezeichnet.

• Für $1561 \le L \le 12\,000$ beträgt die Punktzahl $\left\lfloor \dfrac{100\,000}{L-560} \right\rfloor$.
• Für $0 \le L \le 1560$ beträgt die Punktzahl 100.

Dabei bezeichnet $\lfloor x \rfloor$ die größte ganze Zahl, die nicht größer als $x$ ist.

Beispielkommunikation

Hier sind eine Beispieleingabe für den Beispielgrader und die zugehörigen Funktionsaufrufe.

Eingabe 1

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

Beispielfunktionsaufrufe

Ein kürzester Weg von Stadt $0$ zu Stadt $1$ ergibt sich entweder durch das Durchlaufen der Straßen $1$ und $0$ in dieser Reihenfolge oder allein durch Straße $2$. Daher ist es beim zweiten Aufruf der Funktion answer in diesem Beispiel auch zulässig, answer([2]) aufzurufen.

Die von der Wettbewerbswebsite herunterladbare Datei sample-01-in.txt entspricht Beispieleingabe 1.

Die in den herunterladbaren Dateien der Wettbewerbswebsite enthaltenen Dateien sample-01-in.txt und sample-02-in.txt können als Eingabe für den Beispielgrader verwendet werden.