Aoi og Bitaro eru njósnarar sem tilheyra Upplýsingastofnun ríkisins í JOI-landi. Verkefni þeirra að þessu sinni er að framkvæma leynilega rannsókn í IOI-landi. Bitaro laumast inn í IOI-land á meðan Aoi gefur Bitaro fyrirmæli frá JOI-landi.

Áður en Bitaro laumaðist inn komust Aoi og Bitaro yfir kort af IOI-landi. Í IOI-landi eru $N$ borgir, númeraðar frá $0$ til $N-1$. Enn fremur eru $M$ vegir í IOI-landi, númeraðir frá $0$ til $M-1$. Vegur $i$ ($0\le i\le M-1$) tengir borg $A_i$ og borg $B_i$ í báðar áttir og hefur lengdina $C_i$. Hægt er að ferðast á milli hvaða tveggja borga sem er með því að fara um nokkra vegi. Bitaro ferðast á milli borga í IOI-landi með því að fara um þessa vegi.

Að auki eru $Q$ rannsóknaráætlanir. $j$-ta áætlunin ($0\le j\le Q-1$) felur í sér að rannsaka borg $T_j$ í IOI-landi.

Allar upplýsingarnar hér að ofan voru fyrst látnar bæði Aoi og Bitaro í té. Síðan hélt Bitaro áfram og laumaðist inn í IOI-land.

Bitaro tókst að komast undan fjölmörgum eltingarmönnum, sigraði leigumorðingja og tókst loks að laumast inn í borg $0$ í IOI-landi. Hins vegar, vegna þess hve erfið aðgerðin var, týndi Bitaro hluta af upplýsingunum um IOI-land. Nánar tiltekið týndi Bitaro upplýsingum um lengd $K$ vega, þ.e. veganna $X_0,X_1,\ldots,X_{K-1}$. Með öðrum orðum veit Bitaro ekki lengur gildin á $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Athugið að þótt Bitaro hafi týnt þessum upplýsingum, þá býr Aoi enn yfir þeim.

Bitaro tilkynnti Aoi samstundis hvaða vegalengdaupplýsingum hann hefði týnt.

Til að ljúka verkefninu vill Bitaro vita stystu leið frá borg $0$ til hverrar borgar sem er skotmark í rannsóknaráætlununum $Q$.

Aoi mun senda Bitaro streng þar sem hvert stafmerki er annaðhvort 0 eða 1 til að aðstoða hann. Vegna hættu á hlerunum vill Aoi lágmarka innihaldið sem sent er til Bitaro.

Skrifaðu forrit sem útfærir aðferð Aoi til að senda streng til Bitaro, miðað við upplýsingarnar um IOI-land, rannsóknaráætlanirnar og vegina sem Bitaro týndi upplýsingum um. Skrifaðu einnig forrit sem útfærir aðferð Bitaro til að finna stystu leiðirnar miðað við þær upplýsingar sem hann býr yfir og strenginn sem Aoi sendi.

Útfærsluatriði

Þú átt að skila inn 2 skrám.

Fyrri skráin er Aoi.cpp. Þessi skrá er ætluð til að útfæra aðferð Aoi og á að útfæra eftirfarandi föll. Forritið á að innifela Aoi.h með forvinnslutilskipuninni #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)

Þetta fall er aðeins kallað einu sinni fyrir hvert prófunartilvik.

• Stikinn N er fjöldi borga í IOI-konungsríkinu $N$.
• Stikinn M er fjöldi vega í IOI-konungsríkinu $M$.
• Stikinn Q er fjöldi rannsóknaráætlana $Q$.
• Stikinn K er fjöldi vega sem Bitaro týndi lengdarupplýsingum um, táknaður með $K$.
• Stikarnir A, B, C eru fylki af lengd $M$. Þeir þýða að vegur $i$ ($0\le i\le M-1$) tengir borgina A[i] og borgina B[i] í báðar áttir, með lengdina C[i].
• Stikinn T er fylki af lengd $Q$. Hann þýðir að $j$-ta áætlunin ($0\le j\le Q-1$) felur í sér að rannsaka borg T[j].
• Stikinn X er fylki af lengd $K$. Hann gefur til kynna að Bitaro hafi týnt lengdarupplýsingum um vegina X[0], X[1], ..., X[K-1].
• Skilagildið er strengurinn $s$ sem Aoi sendir til Bitaro.
• Hvert stafmerki í strengnum $s$ verður að vera annaðhvort 0 eða 1. Ef þetta skilyrði er ekki uppfyllt verður forritið þitt dæmt sem Wrong Answer [1].
• Lengd strengsins $s$ má í mesta lagi vera $12\,000$. Ef þetta skilyrði er ekki uppfyllt verður forritið þitt dæmt sem Wrong Answer [2].

Seinni skráin er Bitaro.cpp. Þessi skrá er ætluð til að útfæra aðferð Bitaro og á að útfæra eftirfarandi föll. Forritið á að innifela Bitaro.h með forvinnslutilskipuninni #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)

Þetta fall er aðeins kallað einu sinni eftir að búið er að kalla á fallið aoi.

• Stikinn N er fjöldi borga í IOI-konungsríkinu $N$.
• Stikinn M er fjöldi vega í IOI-konungsríkinu $M$.
• Stikinn Q er fjöldi rannsóknaráætlana $Q$.
• Stikinn K er fjöldi vega sem Bitaro týndi lengdarupplýsingum um, táknaður með $K$.
• Stikarnir A, B, C eru fylki af lengd $M$. Þeir þýða að vegur $i$ ($0\le i\le M-1$) tengir borgina A[i] og borgina B[i] í báðar áttir, með lengdina C[i].
• Stikinn T er fylki af lengd $Q$. Hann þýðir að $j$-ta áætlunin ($0\le j\le Q-1$) felur í sér að rannsaka borg T[j].
• Stikinn X er fylki af lengd $K$. Hann gefur til kynna að Bitaro hafi týnt lengdarupplýsingum um vegina X[0], X[1], ..., X[K-1].
• Viðfangið s er strengur þar sem hvert stafmerki er annaðhvort 0 eða 1, sem táknar strenginn sem Aoi sendi til Bitaro.

Innan Bitaro.cpp getur forritið þitt kallað á eftirfarandi fall.

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

Í $(j+1)$-ta kallinu ($0\le j\le Q-1$) á þetta fall þarftu að svara með stystu leiðinni frá borg $0$ til borgar $T_j$, sem er skotmark $j$-tu rannsóknaráætlunarinnar.

• Stikinn e er fylki sem táknar stystu leiðina frá borg $0$ til borgar $T_j$.
• Látum $n$ vera lengd fylkisins e. Stökin e[0], e[1], ..., e[n-1] eru vísar veganna á stystu leiðinni frá borg $0$ til borgar $T_j$, í þeirri röð sem farið er um þá.
• Ef fleiri en ein stysta leið kemur til greina má velja hvaða sem er af þeim sem svar.
• Hvert stak í stikanum e verður að vera á milli $0$ og $M-1$. Ef þetta skilyrði er ekki uppfyllt verður forritið þitt dæmt sem Wrong Answer [3].

• Runan af vegum sem viðfangið e gefur til kynna verður að mynda veg frá borg $0$ til borgar $T_j$. Formlegra sagt verður hún að uppfylla eftirfarandi skilyrði.

  Til er talnaruna $u_0,u_1,\ldots,u_n$ þannig að

  • $u_0=0$.
  • $u_n=T_j$.
  • Vegurinn e[k] (þar sem $0\le k\le n-1$) tengir borg $u_k$ og borg $u_{k+1}$.

  Ef þessi skilyrði eru ekki uppfyllt verður forritið þitt dæmt sem Wrong Answer [4].

• Ef runan af vegum sem viðfangið e gefur til kynna er ekki stysta leiðin frá borg $0$ til borgar $T_j$ af öllum leiðum sem byrja í borg $0$ og enda í borg $T_j$, verður forritið þitt dæmt sem Wrong Answer [5]. Hér er lengd leiðarinnar skilgreind sem summa lengda veganna sem notaðir eru.

• Kalla verður á fallið answer nákvæmlega $Q$ sinnum. Ef fjöldi kalla á fallið answer er ekki jafn $Q$ í lok keyrslu fallsins bitaro, verður forritið þitt dæmt sem Wrong Answer [6].

Mikilvægar tilkynningar

• Forritið þitt getur útfært önnur föll til innri nota eða notað víðværar breytur (global variables). Innsendar skrár verða þýddar saman við prófarann (grader) og verða að einni keyrsluskrá. Allar víðværar breytur og innri föll ættu að vera skilgreind í nafnlausu nafnarými (unnamed namespace) til að forðast árekstra við aðrar skrár. Þegar það er metið verður það keyrt sem tvö ferli fyrir Aoi og Bitaro. Ferli Aoi og ferli Bitaro geta ekki deilt víðværum breytum.
• Forritið þitt má ekki nota staðalinntak og staðalúttak. Forritið þitt má ekki eiga samskipti við aðrar skrár með neinum aðferðum. Hins vegar má forritið þitt skrifa villuleitarupplýsingar í staðalvilluúttak (standard error).

Þýðing og prófunarkeyrsla

Þú getur sótt safnskrá af vefsíðu keppninnar sem inniheldur sýnisprófarann til að prófa forritið þitt. Safnskráin inniheldur einnig sýniskóðaskrá fyrir forritið þitt.

Sýnisprófarinn er skráin grader.cpp. Til að prófa forritið þitt skaltu setja grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h í sömu möppu og keyra eftirfarandi skipun til að þýða forritin þín. Einnig getur þú keyrt compile.sh sem er í safnskránni.

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

Þegar þýðingin tekst verður keyrsluskráin grader búin til.

Athugaðu að raunverulegi prófarinn er ólíkur sýnisprófaranum. Sýnisprófarinn verður keyrður sem eitt ferli sem les inntaksgögn úr staðalinntaki og skrifar niðurstöðurnar í staðalúttak og staðalvilluúttak.

Inntak fyrir sýnisprófarann

Sýnisprófarinn les eftirfarandi gögn úr staðalinntaki.

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

Úttak sýnisprófarans

Sýnisprófarinn skrifar eftirfarandi upplýsingar í staðalúttak og staðalvilluúttak (gæsalappir til skýringar).

• Ef forritið þitt er dæmt sem Wrong Answer [1], [2], [3], [4] eða [6], skrifar sýnisprófarinn tegundina sem Wrong Answer [1] í staðalvilluúttakið. Ekkert verður skrifað í staðalúttakið.
• Ef ekki, verður lengd strengsins $s$ sem fallið aoi skilar skrifuð í staðalvilluúttakið á sniðinu Accepted: 2024. Að auki verður lengd leiðarinnar í $(j+1)$-ta kallinu ($0\le j\le Q-1$) á fallið answer skrifuð í $(j+1)$-tu línu staðalúttaksins. Sýnisprófunarforritið athugar ekki hvort leiðin sé sú stysta.

Ef forritið þitt uppfyllir skilyrði fyrir fleiri en eina tegund af Wrong Answer tilkynnir sýnisprófarinn aðeins eina þeirra.

Skorður

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

• $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$).
• Hægt er að ferðast frá hvaða borg sem er til hvaða annarrar borgar sem er með því að fara um nokkra vegi.
• Öll inntaksgildi eru heiltölur.

Stigagjöf

Ef forritið þitt er dæmt sem einhver tegund af Wrong Answer [1]–[6] (sjá Útfærsluatriði) eða einhver tegund af keyrsluvillum (TLE (Time Limit Exceeded), MLE (Memory Limit Exceeded), óeðlileg lokun o.s.frv.) í einhverju prófunartilvikanna, þá færðu $0$ stig.

Annars byggist stigagjöfin á hámarkslengd strengsins $s$ sem fallið aoi skilar, táknaðri sem $L$, yfir öll prófunartilvik í þessu verkefni.

• Ef $1561\le L\le12\,000$, eru stigin $\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor$ stig.
• Ef $0\le L\le1560$, eru stigin $100$ stig.

Hér táknar $\lfloor x\rfloor$ stærstu heiltölu sem er ekki stærri en $x$.

Dæmi

Hér er dæmainntak fyrir sýnisprófarann og samsvarandi fallaköll.

Inntak 1

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

Sýnidæmi um fallaköll

Stysta leiðin frá borg $0$ til borgar $1$ fæst annaðhvort með því að fara um vegi $1$ og $0$ í þessari röð, eða einfaldlega með því að fara um veg $2$. Því er einnig leyfilegt fyrir annað kallið á fallið answer í þessu dæmi að kalla á answer([2]).

Skráin sem hægt er að sækja af keppnisvefnum, sample-01-in.txt, samsvarar inntaksdæmi 1.

Skrárnar sample-01-in.txt og sample-02-in.txt sem fylgja með í niðurhalanlegu skránum af keppnisvefnum er hægt að nota sem inntak fyrir sýnisprófarann.