Aoi og Bitaro er spioner som tilhører det nasjonale etterretningsbyrået i landet JOI. Oppdraget deres denne gangen er å gjennomføre en hemmelig etterforskning i landet IOI. Bitaro infiltrerer landet IOI, mens Aoi gir instruksjoner til Bitaro fra landet JOI.

Før infiltrasjonen skaffet Aoi og Bitaro seg et kart over landet IOI. Landet IOI har $N$ byer, nummerert fra $0$ til $N-1$. Videre er det $M$ veier i landet IOI, nummerert fra $0$ til $M-1$. Vei $i$ ($0\le i\le M-1$) forbinder by $A_i$ og by $B_i$ i begge retninger, med en lengde på $C_i$. Det er mulig å reise mellom ethvert par av byer ved å passere noen veier. Bitaro beveger seg mellom byene i landet IOI ved å passere disse veiene.

I tillegg er det $Q$ etterforskningsplaner. Den $j$-te planen ($0\le j\le Q-1$) innebærer å etterforske by $T_j$ i landet IOI.

All informasjonen ovenfor ble først gitt til både Aoi og Bitaro. Deretter gikk Bitaro videre med infiltrasjonen i landet IOI.

Bitaro klarte å unnslippe en rekke forfølgere, beseiret leiemordere og klarte til slutt å infiltrere by $0$ i landet IOI. Men på grunn av infiltrasjonsoperasjonens ekstremt vanskelige natur mistet Bitaro noe av informasjonen om landet IOI. Mer spesifikt mistet Bitaro informasjon om lengden på $K$ veier, nemlig veiene $X_0,X_1,\ldots,X_{K-1}$. Med andre ord kjenner ikke Bitaro lenger verdiene til $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Merk at selv om Bitaro mistet denne informasjonen, har Aoi den fortsatt.

Bitaro rapporterte umiddelbart til Aoi hvilke veilengder han hadde mistet informasjonen om.

For å fullføre oppdraget ønsker Bitaro å vite en korteste vei fra by $0$ til hver av byene som er mål for de $Q$ etterforskningsplanene.

Aoi vil sende Bitaro en streng der hvert tegn er enten 0 eller 1 for å hjelpe ham. På grunn av risikoen for avlytting ønsker Aoi å minimere innholdet som sendes til Bitaro.

Skriv et program for å implementere Aois strategi for å sende en streng til Bitaro, gitt informasjonen om landet IOI, etterforskningsplanene og veiene Bitaro mistet informasjon om. Skriv også et program for å implementere Bitaros strategi for å finne de korteste veiene gitt informasjonen han har og strengen sendt av Aoi.

Implementasjonsdetaljer

Du skal sende inn 2 filer.

Den første filen er Aoi.cpp. Denne filen er ment å implementere Aois strategi og skal implementere følgende funksjoner. Programmet skal inkludere Aoi.h ved hjelp av preprosessordirektivet #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)

Denne funksjonen kalles kun én gang for hvert testtilfelle.

• Parameteren N er antallet byer i kongeriket IOI $N$.
• Parameteren M er antallet veier i kongeriket IOI $M$.
• Parameteren Q er antallet etterforskningsplaner $Q$.
• Parameteren K er antallet veier som Bitaro mistet lengdeinformasjonen om, betegnet med $K$.
• Parameterne A, B, C er tabeller av lengde $M$. De betyr at vei $i$ ($0\le i\le M-1$) forbinder byen A[i] og byen B[i] i begge retninger, med en lengde på C[i].
• Parameteren T er en tabell av lengde $Q$. Den betyr at den $j$-te planen ($0\le j\le Q-1$) innebærer å etterforske by T[j].
• Parameteren X er en tabell av lengde $K$. Den angir at Bitaro mistet lengdeinformasjonen om veiene X[0], X[1], ..., X[K-1].
• Returverdien er strengen $s$ som Aoi sender til Bitaro.
• Hvert tegn i strengen $s$ må være enten 0 eller 1. Hvis denne betingelsen ikke er oppfylt, vil programmet ditt bli bedømt som Wrong Answer [1].
• Lengden på strengen $s$ må være høyst $12\,000$. Hvis denne betingelsen ikke er oppfylt, vil programmet ditt bli bedømt som Wrong Answer [2].

Den andre filen er Bitaro.cpp. Denne filen er ment å implementere Bitaros strategi og skal implementere følgende funksjoner. Programmet skal inkludere Bitaro.h ved hjelp av preprosessordirektivet #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)

Denne funksjonen kalles kun én gang etter at funksjonen aoi er kalt.

• Parameteren N er antallet byer i kongeriket IOI $N$.
• Parameteren M er antallet veier i kongeriket IOI $M$.
• Parameteren Q er antallet etterforskningsplaner $Q$.
• Parameteren K er antallet veier som Bitaro mistet lengdeinformasjonen om, betegnet med $K$.
• Parameterne A, B, C er tabeller av lengde $M$. De betyr at vei $i$ ($0\le i\le M-1$) forbinder byen A[i] og byen B[i] i begge retninger, med en lengde på C[i].
• Parameteren T er en tabell av lengde $Q$. Den betyr at den $j$-te planen ($0\le j\le Q-1$) innebærer å etterforske by T[j].
• Parameteren X er en tabell av lengde $K$. Den angir at Bitaro mistet lengdeinformasjonen om veiene X[0], X[1], ..., X[K-1].
• Argumentet s er en streng der hvert tegn er enten 0 eller 1, som representerer strengen sendt av Aoi til Bitaro.

Inne i Bitaro.cpp kan programmet ditt kalle følgende funksjon.

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

I det $(j+1)$-te kallet ($0\le j\le Q-1$) til denne funksjonen må du svare med den korteste veien fra by $0$ til by $T_j$, som er målet for den $j$-te etterforskningsplanen.

• Parameteren e er en tabell som representerer den korteste veien fra by $0$ til by $T_j$.
• La $n$ være lengden på tabellen e. Elementene e[0], e[1], ..., e[n-1] er indeksene til veiene i den korteste veien fra by $0$ til by $T_j$, i den rekkefølgen de krysses.
• Hvis det finnes flere mulige korteste veier, kan hvilken som helst av dem velges som svar.
• Hvert element i parameteren e må være mellom $0$ og $M-1$. Hvis denne betingelsen ikke er oppfylt, vil programmet ditt bli bedømt som Wrong Answer [3].

• Sekvensen av veier angitt av argumentet e må danne en vei fra by $0$ til by $T_j$. Mer formelt må den tilfredsstille følgende betingelser.

  Det finnes en tallfølge $u_0,u_1,\ldots,u_n$ slik at

  • $u_0=0$.
  • $u_n=T_j$.
  • Veien e[k] (der $0\le k\le n-1$) forbinder by $u_k$ og by $u_{k+1}$.

  Hvis disse betingelsene ikke er oppfylt, vil programmet ditt bli bedømt som Wrong Answer [4].

• Hvis sekvensen av veier angitt av argumentet e ikke er den korteste veien fra by $0$ til by $T_j$ blant alle veier som starter i by $0$ og slutter i by $T_j$, vil programmet ditt bli bedømt som Wrong Answer [5]. Her er lengden på veien definert som summen av lengdene til veiene som brukes.

• Funksjonen answer må kalles nøyaktig $Q$ ganger. Hvis antallet kall til funksjonen answer ikke er lik $Q$ ved slutten av kjøringen av funksjonen bitaro, vil programmet ditt bli bedømt som Wrong Answer [6].

Viktige merknader

• Programmet ditt kan implementere andre funksjoner for internt bruk, eller bruke globale variabler. Innsendte filer vil bli kompilert sammen med graderen, og bli én enkelt kjørbar fil. Alle globale variabler og interne funksjoner bør deklareres i et navnløst navnerom (unnamed namespace) for å unngå konflikter med andre filer. Når det bedømmes, vil det bli kjørt som to prosesser for Aoi og Bitaro. Prosessen til Aoi og prosessen til Bitaro kan ikke dele globale variabler.
• Programmet ditt må ikke bruke standard inndata og standard utdata. Programmet ditt må ikke kommunisere med andre filer på noen måte. Programmet ditt kan imidlertid skrive ut feilsøkingsinformasjon til standard feilutdata (standard error).

Kompilering og testkjøring

Du kan laste ned en arkivfil fra konkurransens nettside som inneholder eksempelgraderen for å teste programmet ditt. Arkivfilen inneholder også en eksempelkildefil for programmet ditt.

Eksempelgraderen er filen grader.cpp. For å teste programmet ditt, legg grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h i samme mappe, og kjør følgende kommando for å kompilere programmene dine. Alternativt kan du kjøre compile.sh som ligger i arkivfilen.

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

Når kompileringen lykkes, genereres den kjørbare filen grader.

Merk at den faktiske graderen er forskjellig fra eksempelgraderen. Eksempelgraderen vil bli kjørt som én enkelt prosess, som vil lese inndata fra standard inndata og skrive resultatene til standard utdata og standard feilutdata.

Inndata for eksempelgraderen

Eksempelgraderen leser følgende data fra standard inndata.

$$ \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 fra eksempelgraderen

Eksempelgraderen skriver ut følgende informasjon til standard utdata og standard feilutdata (anførselstegn for klarhet).

• Hvis programmet ditt blir bedømt som Wrong Answer [1], [2], [3], [4] eller [6], skriver eksempelgraderen typen som Wrong Answer [1] til standard feilutdata. Ingenting vil bli skrevet ut til standard utdata.
• Hvis ikke, vil lengden på den returnerte strengen $s$ fra funksjonen aoi bli skrevet ut til standard feilutdata i formatet Accepted: 2024. I tillegg vil lengden på veien i det $(j+1)$-te kallet ($0\le j\le Q-1$) til answer-funksjonen bli skrevet ut på den $(j+1)$-te linjen i standard utdata. Eksempelbedømmingsprogrammet sjekker ikke om veien er den korteste.

Hvis programmet ditt oppfyller betingelsene for flere typer Wrong Answer, rapporterer eksempelgraderen bare én av dem.

Begrensninger

Alle inndata tilfredsstiller følgende betingelser:

• $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 reise fra hvilken som helst by til hvilken som helst annen by ved å krysse noen veier.
• Alle inndataverdier er heltall.

Poengberegning

Hvis programmet ditt blir bedømt som en hvilken som helst type Wrong Answer [1]–[6] (se Implementasjonsdetaljer) eller en hvilken som helst type kjøretidsfeil (TLE (Time Limit Exceeded), MLE (Memory Limit Exceeded), unormal avslutning, osv.) i noen av testtilfellene, er poengsummen din $0$ poeng.

Ellers er poengberegningen basert på den maksimale lengden av den returnerte strengen $s$ fra funksjonen aoi, betegnet som $L$, over alle testtilfeller for denne oppgaven.

• Hvis $1561\le L\le12\,000$, er poengsummen $\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor$ poeng.
• Hvis $0\le L\le1560$, er poengsummen $100$ poeng.

Her representerer $\lfloor x\rfloor$ det største heltallet som ikke er større enn $x$.

Eksempler

Her er eksempeldata for eksempelgraderen og tilhørende funksjonskall.

Inndata 1

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

Eksempel på funksjonskall

Den korteste veien fra by $0$ til by $1$ oppnås enten ved å krysse veiene $1$ og $0$ i denne rekkefølgen, eller rett og slett ved å gå gjennom vei $2$. Derfor er det for det andre kallet til answer-funksjonen i dette eksempelet også akseptabelt å kalle answer([2]).

Filen som kan lastes ned fra konkurransesiden, sample-01-in.txt, tilsvarer inndataeksempel 1.

Filene sample-01-in.txt og sample-02-in.txt som er inkludert i de nedlastbare filene fra konkurransesiden, kan brukes som inndata for eksempelgraderen.