Aoi ja Bitaro ovat JOI-maan kansalliseen tiedustelutoimistoon kuuluvia vakoojia. Heidän tehtävänään on tällä kertaa suorittaa peitetutkinta IOI-maahan. Bitaro soluttautuu IOI-maahan, kun taas Aoi antaa Bitarolle ohjeita JOI-maasta käsin.

Ennen soluttautumista Aoi ja Bitaro saivat haltuunsa IOI-maan kartan. IOI-maassa on $N$ kaupunkia, jotka on numeroitu $0$:sta $N-1$:een. Lisäksi IOI-maassa on $M$ tietä, jotka on numeroitu $0$:sta $M-1$:een. Tie $i$ ($0\le i\le M-1$) yhdistää kaupungin $A_i$ ja kaupungin $B_i$ kaksisuuntaisesti, ja sen pituus on $C_i$. Minkä tahansa kahden kaupungin välillä on mahdollista matkustaa kulkemalla joitakin teitä pitkin. Bitaro liikkuu IOI-maan kaupunkien välillä kulkemalla näitä teitä pitkin.

Lisäksi on $Q$ tutkintasuunnitelmaa. $j$:s suunnitelma ($0\le j\le Q-1$) sisältää IOI-maan kaupungin $T_j$ tutkimisen.

Kaikki yllä olevat tiedot annettiin aluksi sekä Aoille että Bitarolle. Sen jälkeen Bitaro eteni soluttautumisessa IOI-maahan.

Bitaro onnistui väistämään lukuisia takaa-ajajia, kukisti salamurhaajat ja onnistui lopulta soluttautumaan IOI-maan kaupunkiin $0$. Soluttautumisoperaation äärimmäisen vaikean luonteen vuoksi Bitaro kuitenkin kadotti osan IOI-maata koskevista tiedoista. Tarkemmin sanottuna Bitaro kadotti tiedon $K$ tien pituudesta, nimittäin teiden $X_0,X_1,\ldots,X_{K-1}$. Toisin sanoen Bitaro ei enää tiedä arvoja $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Huomaa, että vaikka Bitaro kadotti nämä tiedot, Aoilla on ne edelleen tallella.

Bitaro ilmoitti välittömästi Aoille, minkä teiden pituustiedot hän oli kadottanut.

Suorittaakseen tehtävän Bitaro haluaa tietää lyhimmän polun kaupungista $0$ kuhunkin $Q$ tutkintasuunnitelman kohteena olevaan kaupunkiin.

Aoi lähettää Bitarolle hänen avukseen merkkijonon, jonka jokainen merkki on joko 0 tai 1. Sieppausriskin vuoksi Aoi haluaa minimoida Bitarolle lähetettävän sisällön.

Kirjoita ohjelma, joka toteuttaa Aoin strategian merkkijonon lähettämiseksi Bitarolle, kun annetaan tiedot IOI-maasta, tutkintasuunnitelmista ja teistä, joiden tiedot Bitaro kadotti. Kirjoita myös ohjelma, joka toteuttaa Bitaron strategian lyhimpien polkujen löytämiseksi, kun annetaan hänen hallussaan olevat tiedot sekä Aoin lähettämä merkkijono.

Toteutuksen yksityiskohdat

Sinun tulee palauttaa 2 tiedostoa.

Ensimmäinen tiedosto on Aoi.cpp. Tämä tiedosto on tarkoitettu Aoin strategian toteuttamiseen, ja siinä tulee toteuttaa seuraavat funktiot. Ohjelman tulee sisällyttää Aoi.h käyttämällä esikääntäjädirektiiviä #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)

Tätä funktiota kutsutaan vain kerran kutakin testitapausta kohti.

• Parametri N on IOI-kuningaskunnan kaupunkien lukumäärä $N$.
• Parametri M on IOI-kuningaskunnan teiden lukumäärä $M$.
• Parametri Q on tutkintasuunnitelmien lukumäärä $Q$.
• Parametri K on niiden teiden lukumäärä, joiden pituustiedot Bitaro kadotti, merkittynä $K$:lla.
• Parametrit A, B, C ovat pituuden $M$ taulukoita. Ne tarkoittavat, että tie $i$ ($0\le i\le M-1$) yhdistää kaupungin A[i] ja kaupungin B[i] kaksisuuntaisesti ja sen pituus on C[i].
• Parametri T on pituuden $Q$ taulukko. Se tarkoittaa, että $j$:s suunnitelma ($0\le j\le Q-1$) sisältää kaupungin T[j] tutkimisen.
• Parametri X on pituuden $K$ taulukko. Se osoittaa, että Bitaro kadotti teiden X[0], X[1], ..., X[K-1] pituustiedot.
• Paluuarvo on merkkijono $s$, jonka Aoi lähettää Bitarolle.
• Merkkijonon $s$ jokaisen merkin on oltava joko 0 tai 1. Jos tämä ehto ei täyty, ohjelmasi tuomitaan tuloksella Wrong Answer [1].
• Merkkijonon $s$ pituus saa olla enintään $12\,000$. Jos tämä ehto ei täyty, ohjelmasi tuomitaan tuloksella Wrong Answer [2].

Toinen tiedosto on Bitaro.cpp. Tämä tiedosto on tarkoitettu Bitaron strategian toteuttamiseen, ja siinä tulee toteuttaa seuraavat funktiot. Ohjelman tulee sisällyttää Bitaro.h käyttämällä esikääntäjädirektiiviä #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)

Tätä funktiota kutsutaan vain kerran sen jälkeen, kun funktiota aoi on kutsuttu.

• Parametri N on IOI-kuningaskunnan kaupunkien lukumäärä $N$.
• Parametri M on IOI-kuningaskunnan teiden lukumäärä $M$.
• Parametri Q on tutkintasuunnitelmien lukumäärä $Q$.
• Parametri K on niiden teiden lukumäärä, joiden pituustiedot Bitaro kadotti, merkittynä $K$:lla.
• Parametrit A, B, C ovat pituuden $M$ taulukoita. Ne tarkoittavat, että tie $i$ ($0\le i\le M-1$) yhdistää kaupungin A[i] ja kaupungin B[i] kaksisuuntaisesti ja sen pituus on C[i].
• Parametri T on pituuden $Q$ taulukko. Se tarkoittaa, että $j$:s suunnitelma ($0\le j\le Q-1$) sisältää kaupungin T[j] tutkimisen.
• Parametri X on pituuden $K$ taulukko. Se osoittaa, että Bitaro kadotti teiden X[0], X[1], ..., X[K-1] pituustiedot.
• Argumentti s on merkkijono, jonka jokainen merkki on joko 0 tai 1, ja se edustaa Aoin Bitarolle lähettämää merkkijonoa.

Tiedoston Bitaro.cpp sisällä ohjelmasi voi kutsua seuraavaa funktiota.

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

Tämän funktion $(j+1)$:nnessä kutsussa ($0\le j\le Q-1$) sinun on vastattava lyhimmällä polulla kaupungista $0$ kaupunkiin $T_j$, joka on $j$:nnen tutkintasuunnitelman kohde.

• Parametri e on taulukko, joka edustaa lyhintä polkua kaupungista $0$ kaupunkiin $T_j$.
• Olkoon $n$ taulukon e pituus. Alkiot e[0], e[1], ..., e[n-1] ovat kaupungista $0$ kaupunkiin $T_j$ kulkevan lyhimmän polun teiden indeksit kulkujärjestyksessä.
• Jos mahdollisia lyhimpiä polkuja on useita, mikä tahansa niistä voidaan valita vastaukseksi.
• Parametrin e jokaisen alkion on oltava välillä $0$ – $M-1$. Jos tämä ehto ei täyty, ohjelmasi tuomitaan tuloksella Wrong Answer [3].

• Argumentin e osoittaman teiden jonon on muodostettava polku kaupungista $0$ kaupunkiin $T_j$. Muodollisemmin sen on täytettävä seuraavat ehdot.

  On olemassa lukujono $u_0,u_1,\ldots,u_n$ siten, että

  • $u_0=0$.
  • $u_n=T_j$.
  • Tie e[k] (missä $0\le k\le n-1$) yhdistää kaupungin $u_k$ ja kaupungin $u_{k+1}$.

  Jos nämä ehdot eivät täyty, ohjelmasi tuomitaan tuloksella Wrong Answer [4].

• Jos argumentin e osoittama teiden jono ei ole lyhin polku kaupungista $0$ kaupunkiin $T_j$ kaikkien kaupungista $0$ alkavien ja kaupunkiin $T_j$ päättyvien polkujen joukossa, ohjelmasi tuomitaan tuloksella Wrong Answer [5]. Tässä polun pituus määritellään käytettyjen teiden pituuksien summana.

• Funktiota answer on kutsuttava täsmälleen $Q$ kertaa. Jos funktion answer kutsujen lukumäärä ei ole yhtä suuri kuin $Q$ funktion bitaro suorituksen päättyessä, ohjelmasi tuomitaan tuloksella Wrong Answer [6].

Tärkeitä huomautuksia

• Ohjelmasi voi toteuttaa muita funktioita sisäiseen käyttöön tai käyttää globaaleja muuttujia. Palautetut tiedostot käännetään tarkistimen (grader) kanssa, ja niistä tulee yksi suoritettava tiedosto. Kaikki globaalit muuttujat ja sisäiset funktiot tulee esitellä nimettömässä nimiavaruudessa (unnamed namespace) ristiriitojen välttämiseksi muiden tiedostojen kanssa. Arvioitaessa se suoritetaan kahtena prosessina Aoille ja Bitarolle. Aoin prosessi ja Bitaron prosessi eivät voi jakaa globaaleja muuttujia.
• Ohjelmasi ei saa käyttää standardisyötettä eikä standarditulostetta. Ohjelmasi ei saa kommunikoida muiden tiedostojen kanssa millään menetelmällä. Ohjelmasi voi kuitenkin tulostaa virheenkorjaustietoja standardivirhetulosteeseen (standard error).

Kääntäminen ja koeajo

Voit ladata kilpailun verkkosivulta arkistotiedoston, joka sisältää esimerkkitarkistimen ohjelmasi testaamista varten. Arkistotiedosto sisältää myös ohjelmasi esimerkkilähdekooditiedoston.

Esimerkkitarkistin on tiedosto grader.cpp. Testataksesi ohjelmaasi laita grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h samaan hakemistoon ja suorita seuraava komento ohjelmiesi kääntämiseksi. Vaihtoehtoisesti voit suorittaa arkistotiedostossa olevan tiedoston compile.sh.

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

Kun käännös onnistuu, luodaan suoritettava tiedosto grader.

Huomaa, että varsinainen tarkistin eroaa esimerkkitarkistimesta. Esimerkkitarkistin suoritetaan yhtenä prosessina, joka lukee syötetiedot standardisyötteestä ja kirjoittaa tulokset standarditulosteeseen ja standardivirhetulosteeseen.

Esimerkkitarkistimen syöte

Esimerkkitarkistin lukee seuraavat tiedot standardisyötteestä.

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

Esimerkkitarkistimen tuloste

Esimerkkitarkistin tulostaa seuraavat tiedot standarditulosteeseen ja standardivirhetulosteeseen (lainausmerkit selvyyden vuoksi).

• Jos ohjelmasi tuomitaan tuloksella Wrong Answer [1], [2], [3], [4] tai [6], esimerkkitarkistin kirjoittaa sen tyypin muodossa Wrong Answer [1] standardivirhetulosteeseen. Standarditulosteeseen ei tulosteta mitään.
• Muussa tapauksessa funktiosta aoi palautetun merkkijonon $s$ pituus tulostetaan standardivirhetulosteeseen muodossa Accepted: 2024. Lisäksi polun pituus funktion answer $(j+1)$:nnessä kutsussa ($0\le j\le Q-1$) tulostetaan standarditulosteen $(j+1)$:nnelle riville. Esimerkkiarvosteluohjelma ei tarkista, onko polku lyhin.

Jos ohjelmasi täyttää usean eri Wrong Answer -tyypin ehdot, esimerkkitarkistin ilmoittaa niistä vain yhden.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot:

• $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$).
• Mistä tahansa kaupungista voi matkustaa mihin tahansa toiseen kaupunkiin kulkemalla joitakin teitä pitkin.
• Kaikki syötearvot ovat kokonaislukuja.

Arvostelu

Jos ohjelmasi tuomitaan minkä tahansa tyyppisellä tuloksella Wrong Answer [1]–[6] (katso Toteutuksen yksityiskohdat) tai minkä tahansa tyyppisellä ajonaikaisella virheellä (TLE (aikaylitys), MLE (muistiylitys), epänormaali päättyminen jne.) missä tahansa testitapauksessa, pistemääräsi on $0$ pistettä.

Muussa tapauksessa arvostelu perustuu funktiosta aoi palautetun merkkijonon $s$ suurimpaan pituuteen $L$ kaikissa tämän tehtävän testitapauksissa.

• Jos $1561\le L\le12\,000$, pistemäärä on $\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor$ pistettä.
• Jos $0\le L\le1560$, pistemäärä on $100$ pistettä.

Tässä $\lfloor x\rfloor$ tarkoittaa suurinta kokonaislukua, joka ei ole suurempi kuin $x$.

Esimerkit

Tässä on esimerkkisyöte esimerkkitarkistimelle sekä vastaavat funktiokutsut.

Syöte 1

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

Esimerkkifunktiokutsut

Lyhin polku kaupungista $0$ kaupunkiin $1$ saavutetaan joko kulkemalla tiet $1$ ja $0$ tässä järjestyksessä tai kulkemalla yksinkertaisesti tien $2$ kautta. Siksi tämän esimerkin toisessa answer-funktion kutsussa on hyväksyttävää kutsua myös answer([2]).

Kilpailusivustolta ladattavissa oleva tiedosto sample-01-in.txt vastaa syöte-esimerkkiä 1.

Kilpailusivustolta ladattaviin tiedostoihin sisältyviä tiedostoja sample-01-in.txt ja sample-02-in.txt voidaan käyttää esimerkkitarkistimen syötteenä.