Aoi och Bitaro är spioner som tillhör den nationella underrättelsebyrån i landet JOI. Deras uppdrag den här gången är att genomföra en hemlig undersökning i landet IOI. Bitaro infiltrerar landet IOI, medan Aoi ger instruktioner till Bitaro från landet JOI.

Före infiltrationen fick Aoi och Bitaro tag på en karta över landet IOI. Landet IOI har $N$ städer, numrerade från $0$ till $N-1$. Dessutom finns det $M$ vägar i landet IOI, numrerade från $0$ till $M-1$. Väg $i$ ($0\le i\le M-1$) förbinder stad $A_i$ och stad $B_i$ i båda riktningarna, med en längd på $C_i$. Det är möjligt att resa mellan vilka två städer som helst genom att passera några vägar. Bitaro förflyttar sig mellan städerna i landet IOI genom att passera dessa vägar.

Dessutom finns det $Q$ undersökningsplaner. Den $j$:te planen ($0\le j\le Q-1$) går ut på att undersöka stad $T_j$ i landet IOI.

All information ovan gavs först till både Aoi och Bitaro. Därefter fortsatte Bitaro med infiltrationen i landet IOI.

Bitaro lyckades undkomma ett flertal förföljare, besegrade lönnmördare och lyckades slutligen infiltrera stad $0$ i landet IOI. Men på grund av infiltrationsoperationens extremt svåra natur förlorade Bitaro en del av informationen om landet IOI. Mer specifikt förlorade Bitaro information om längden på $K$ vägar, nämligen vägarna $X_0,X_1,\ldots,X_{K-1}$. Med andra ord känner Bitaro inte längre till värdena på $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Observera att medan Bitaro förlorade denna information, har Aoi fortfarande kvar den.

Bitaro rapporterade omedelbart till Aoi vilka väglängder han hade förlorat informationen om.

För att slutföra uppdraget vill Bitaro veta en kortaste väg från stad $0$ till var och en av städerna som är mål för de $Q$ undersökningsplanerna.

Aoi kommer att skicka en sträng till Bitaro där varje tecken är antingen 0 eller 1 för att hjälpa honom. På grund av risken för avlyssning vill Aoi minimera innehållet som skickas till Bitaro.

Skriv ett program för att implementera Aois strategi för att skicka en sträng till Bitaro, givet informationen om landet IOI, undersökningsplanerna och vägarna som Bitaro förlorade information om. Skriv också ett program för att implementera Bitaros strategi för att hitta de kortaste vägarna givet informationen han har och strängen som skickats av Aoi.

Implementationsdetaljer

Du ska skicka in 2 filer.

Den första filen är Aoi.cpp. Denna fil är avsedd att implementera Aois strategi och ska implementera följande funktioner. Programmet ska inkludera Aoi.h med hjälp av preprocessordirektivet #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)

Denna funktion anropas endast en gång för varje testfall.

• Parametern N är antalet städer i kungariket IOI $N$.
• Parametern M är antalet vägar i kungariket IOI $M$.
• Parametern Q är antalet undersökningsplaner $Q$.
• Parametern K är antalet vägar som Bitaro förlorade längdinformationen om, betecknat med $K$.
• Parametrarna A, B, C är arrayer av längd $M$. De betyder att väg $i$ ($0\le i\le M-1$) förbinder staden A[i] och staden B[i] i båda riktningarna, med en längd på C[i].
• Parametern T är en array av längd $Q$. Den betyder att den $j$:te planen ($0\le j\le Q-1$) går ut på att undersöka stad T[j].
• Parametern X är en array av längd $K$. Den anger att Bitaro förlorade längdinformationen om vägarna X[0], X[1], ..., X[K-1].
• Returvärdet är strängen $s$ som Aoi skickar till Bitaro.
• Varje tecken i strängen $s$ måste vara antingen 0 eller 1. Om detta villkor inte uppfylls kommer ditt program att bedömas som Wrong Answer [1].
• Längden på strängen $s$ får vara högst $12\,000$. Om detta villkor inte uppfylls kommer ditt program att bedömas som Wrong Answer [2].

Den andra filen är Bitaro.cpp. Denna fil är avsedd att implementera Bitaros strategi och ska implementera följande funktioner. Programmet ska inkludera Bitaro.h med hjälp av preprocessordirektivet #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)

Denna funktion anropas endast en gång efter att funktionen aoi har anropats.

• Parametern N är antalet städer i kungariket IOI $N$.
• Parametern M är antalet vägar i kungariket IOI $M$.
• Parametern Q är antalet undersökningsplaner $Q$.
• Parametern K är antalet vägar som Bitaro förlorade längdinformationen om, betecknat med $K$.
• Parametrarna A, B, C är arrayer av längd $M$. De betyder att väg $i$ ($0\le i\le M-1$) förbinder staden A[i] och staden B[i] i båda riktningarna, med en längd på C[i].
• Parametern T är en array av längd $Q$. Den betyder att den $j$:te planen ($0\le j\le Q-1$) går ut på att undersöka stad T[j].
• Parametern X är en array av längd $K$. Den anger att Bitaro förlorade längdinformationen om vägarna X[0], X[1], ..., X[K-1].
• Argumentet s är en sträng där varje tecken är antingen 0 eller 1, vilket representerar strängen som skickats av Aoi till Bitaro.

Inuti Bitaro.cpp kan ditt program anropa följande funktion.

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

I det $(j+1)$:a anropet ($0\le j\le Q-1$) till denna funktion måste du svara med den kortaste vägen från stad $0$ till stad $T_j$, som är målet för den $j$:te undersökningsplanen.

• Parametern e är en array som representerar den kortaste vägen från stad $0$ till stad $T_j$.
• Låt $n$ vara längden på arrayen e. Elementen e[0], e[1], ..., e[n-1] är indexen för vägarna i den kortaste vägen från stad $0$ till stad $T_j$, i den ordning de passeras.
• Om det finns flera möjliga kortaste vägar kan vilken som helst av dem väljas som svar.
• Varje element i parametern e måste ligga mellan $0$ och $M-1$. Om detta villkor inte uppfylls kommer ditt program att bedömas som Wrong Answer [3].

• Sekvensen av vägar som anges av argumentet e måste utgöra en väg från stad $0$ till stad $T_j$. Mer formellt måste den uppfylla följande villkor.

  Det finns en talföljd $u_0,u_1,\ldots,u_n$ sådan att

  • $u_0=0$.
  • $u_n=T_j$.
  • Vägen e[k] (där $0\le k\le n-1$) förbinder stad $u_k$ och stad $u_{k+1}$.

  Om dessa villkor inte uppfylls kommer ditt program att bedömas som Wrong Answer [4].

• Om sekvensen av vägar som anges av argumentet e inte är den kortaste vägen från stad $0$ till stad $T_j$ bland alla vägar som börjar i stad $0$ och slutar i stad $T_j$, kommer ditt program att bedömas som Wrong Answer [5]. Här definieras vägens längd som summan av längderna på de använda vägarna.

• Funktionen answer måste anropas exakt $Q$ gånger. Om antalet anrop till funktionen answer inte är lika med $Q$ i slutet av körningen av funktionen bitaro, kommer ditt program att bedömas som Wrong Answer [6].

Viktiga meddelanden

• Ditt program kan implementera andra funktioner för internt bruk, eller använda globala variabler. Inskickade filer kommer att kompileras tillsammans med gradern och bli en enda körbar fil. Alla globala variabler och interna funktioner bör deklareras i ett namnlöst namnrymd (unnamed namespace) för att undvika konflikter med andra filer. Vid bedömningen kommer det att köras som två processer för Aoi och Bitaro. Aois process och Bitaros process kan inte dela globala variabler.
• Ditt program får inte använda standard in och standard ut. Ditt program får inte kommunicera med andra filer på något sätt. Ditt program får dock skriva ut felsökningsinformation till standard error.

Kompilering och testkörning

Du kan ladda ner en arkivfil från tävlingens webbsida som innehåller exempelgradern för att testa ditt program. Arkivfilen innehåller också en exempelkällfil för ditt program.

Exempelgradern är filen grader.cpp. För att testa ditt program, lägg grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h i samma katalog och kör följande kommando för att kompilera dina program. Alternativt kan du köra compile.sh som finns i arkivfilen.

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

När kompileringen lyckas genereras den körbara filen grader.

Observera att den faktiska gradern skiljer sig från exempelgradern. Exempelgradern kommer att köras som en enda process, som läser indata från standard in och skriver resultaten till standard ut och standard error.

Indata för exempelgradern

Exempelgradern läser följande data från standard in.

$$ \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} $$

Utdata från exempelgradern

Exempelgradern skriver ut följande information till standard ut och standard error (citattecken för tydlighetens skull).

• Om ditt program bedöms som Wrong Answer [1], [2], [3], [4] eller [6], skriver exempelgradern dess typ som Wrong Answer [1] till standard error. Ingenting kommer att skrivas ut till standard ut.
• Om inte, kommer längden på den returnerade strängen $s$ från funktionen aoi att skrivas ut till standard error i formatet Accepted: 2024. Dessutom kommer längden på vägen i det $(j+1)$:a anropet ($0\le j\le Q-1$) till funktionen answer att skrivas ut på den $(j+1)$:a raden i standard ut. Exempelbedömningsprogrammet kontrollerar inte om vägen är den kortaste.

Om ditt program uppfyller villkoren för flera typer av Wrong Answer rapporterar exempelgradern endast en av dem.

Begränsningar

All indata uppfyller följande villkor:

• $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$).
• Du kan resa från vilken stad som helst till vilken annan stad som helst genom att passera några vägar.
• Alla indatavärden är heltal.

Poängsättning

Om ditt program bedöms som någon typ av Wrong Answer [1]–[6] (se Implementationsdetaljer) eller någon typ av körningsfel (TLE (Time Limit Exceeded), MLE (Memory Limit Exceeded), onormalt avslut, etc.) i något av testfallen, blir din poäng $0$ poäng.

Annars baseras poängsättningen på den maximala längden av den returnerade strängen $s$ från funktionen aoi, betecknad som $L$, över alla testfall för denna uppgift.

• Om $1561\le L\le12\,000$ är poängen $\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor$ poäng.
• Om $0\le L\le1560$ är poängen $100$ poäng.

Här representerar $\lfloor x\rfloor$ det största heltalet som inte är större än $x$.

Exempel

Här är en exempelindata för exempelgradern och motsvarande funktionsanrop.

Indata 1

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

Exempel på funktionsanrop

Den kortaste vägen från stad $0$ till stad $1$ uppnås antingen genom att passera vägarna $1$ och $0$ i denna ordning, eller genom att helt enkelt passera väg $2$. För det andra anropet till funktionen answer i detta exempel är det därför också acceptabelt att anropa answer([2]).

Filen som kan laddas ner från tävlingssidan, sample-01-in.txt, motsvarar indataexempel 1.

Filerna sample-01-in.txt och sample-02-in.txt som ingår i de nedladdningsbara filerna från tävlingssidan kan användas som indata för exempelgradern.