On $N$ saarta, joilla asuu majavia, ja ne on numeroitu $0$:sta $N-1$:een. Nämä saaret on yhdistetty $N-1$ kaksisuuntaisella sillalla. Minkä tahansa saarten välillä on mahdollista matkustaa käyttämällä joitakin siltoja. Kullekin saarelle on suoraan kytkettynä enintään 18 siltaa. Jokaisella saarella asuu yksi majava.

Joskus jotkin majavat kokoontuvat jollekin saarelle pitämään kokousta. Kun täsmälleen kolme majavaa tapaa, ne kokoontuvat seuraavalle saarelle:

Saarelle, joka minimoi niiden siltojen kokonaismäärän, joiden yli nämä kolme majavaa kulkevat kokoontuessaan (tällainen saari on yksikäsitteisesti olemassa).

Huomaa, että tämä saari voi olla sama kuin saari, jolla yksi kolmesta majavasta asuu.

Olet kiinnostunut siitä, miten $N$ saarta ovat yhteydessä toisiinsa silloilla. Et voi mennä tarkistamaan saaria suoraan, joten aiot antaa majaville joitakin ohjeita. Yksi ohje on seuraavanlainen:

• Määrittelet kolme saarta $u$, $v$ ja $w$ ($0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$, $v \ne w$), ja laitat saarilla $u$, $v$ ja $w$ asuvat majavat pitämään kokouksen.
• Tällöin näet saaren, jolle nämä kolme majavaa kokoontuvat.

Haluat selvittää mahdollisimman vähillä ohjeilla, miten saaret ovat yhteydessä toisiinsa.

Kirjoita ohjelma, joka saarten lukumäärän perusteella majavien kanssa kommunikoimalla selvittää, miten saaret ovat yhteydessä toisiinsa.

Toteutuksen yksityiskohdat

Sinun tulee palauttaa yksi tiedosto.

Tiedoston nimi on meetings.cpp. Sen tulee toteuttaa seuraava funktio. Ohjelman tulee sisällyttää otsikkotiedosto meetings.h.

• void Solve(int N)

Tätä funktiota kutsutaan täsmälleen kerran jokaiselle testitapaukselle.

• Parametri N ilmaisee saarten lukumäärän $N$.

Ohjelmasi voi kutsua seuraavia funktioita.

• int Query(int u, int v, int w)

Tämä funktio palauttaa määrittämiesi kolmen saaren indekseille sen saaren indeksin, jolle kyseisillä saarilla asuvat majavat kokoontuvat kokoukseen.

• Määrität kolmen saaren indeksit $u$, $v$ ja $w$ vastaavasti parametreilla u, v ja w. Näiden on täytettävä ehdot $0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$ ja $v \ne w$. Muussa tapauksessa ohjelmasi tulokseksi katsotaan Wrong Answer [1].

• Funktiota Query saa kutsua enintään $100\,000$ kertaa. Muussa tapauksessa ohjelmasi tulokseksi katsotaan Wrong Answer [2].

• void Bridge(int u, int v)

Tämän funktion avulla ilmoitat, miten saaret ovat yhteydessä toisiinsa silloilla.

• Parametrit u ja v ilmaisevat, että saaret $u$ ja $v$ ovat suoraan yhteydessä toisiinsa sillalla.
• Jos ehto $0 \le u < v \le N-1$ ei päde, ohjelmasi tulokseksi katsotaan Wrong Answer [3].
• Jos saaret $u$ ja $v$ eivät ole suoraan yhteydessä toisiinsa sillalla, ohjelmasi tulokseksi katsotaan Wrong Answer [4].
• Jos funktiota Bridge kutsutaan samoilla parametreilla u ja v useita kertoja, ohjelmasi tulokseksi katsotaan Wrong Answer [5].
• Koska siltoja on $N-1$, funktiota Bridge on kutsuttava täsmälleen $N-1$ kertaa. Jos funktion Bridge kutsujen määrä ei ole $N-1$ funktion Solve suorituksen päättyessä, ohjelmasi tulokseksi katsotaan Wrong Answer [6].

Tärkeitä huomioita

• Ohjelmasi voi toteuttaa muita funktioita sisäiseen käyttöön tai käyttää 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ää esimerkkitarkastimen ohjelmasi testaamista varten. Arkistotiedosto sisältää myös esimerkkilähdekooditiedoston ohjelmallesi.

Esimerkkitarkastin on tiedosto grader.cpp. Testataksesi ohjelmaasi aseta grader.cpp, meetings.cpp ja meetings.h samaan hakemistoon ja suorita seuraava komento ohjelmiesi kääntämiseksi.

g++ -std=gnu++14 -O2 -o grader grader.cpp meetings.cpp

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

Huomaa, että varsinainen tarkastin eroaa esimerkkitarkastimesta. Esimerkkitarkastin suoritetaan yhtenä prosessina, joka lukee syötetiedot standardisyötteestä ja kirjoittaa tulokset standarditulosteeseen.

Esimerkkitarkastimen syöte

Esimerkkitarkastin lukee seuraavat tiedot standardisyötteestä.

$$ \begin{array}{ll} N & \\ A_0 & B_0 \\ \vdots & \\ A_{N-2} & B_{N-2} \end{array} $$

$A_i$ ja $B_i$ ($0 \le i \le N-2$) ilmaisevat, että saaret $A_i$ ja $B_i$ ovat suoraan yhteydessä toisiinsa sillalla.

Esimerkkitarkastimen tuloste

Kun ohjelman suoritus päättyy onnistuneesti, esimerkkitarkastin kirjoittaa seuraavat tiedot standarditulosteeseen (lainausmerkit selkeyden vuoksi).

• Jos ohjelmasi katsotaan oikeaksi, se tulostaa funktion Query kutsujen määrän muodossa “Accepted: 100”.
• Jos ohjelmasi tulokseksi katsotaan Wrong Answer, se tulostaa sen tyypin muodossa “Wrong Answer [1]”.

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

Rajoitukset

Katso lukujen $A_i$ ja $B_i$ määritelmä osiosta “Esimerkkitarkastimen syöte”.

• $3 \le N \le 2\,000$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• Minkä tahansa saarten välillä on mahdollista matkustaa käyttämällä joitakin siltoja.
• Kullekin saarelle on suoraan kytkettynä enintään 18 siltaa.

Osatehtävät

1. (7 pistettä) $N \le 7$.
2. (10 pistettä) $N \le 50$.
3. (12 pistettä) $N \le 300$.

4. (71 pistettä) Ei lisärajoituksia.

5. Osatehtävissä 1, 2 ja 3 saat täydet pisteet, jos ohjelmasi toimii oikein kaikissa osatehtävän testitapauksissa.

6. Osatehtävässä 4, jos ohjelmasi toimii oikein kaikissa testitapauksissa, pistemääräsi määräytyy seuraavasti, missä $X$ on funktion Query suurin kutsujen määrä yhdessä testitapauksessa:

   • 49 pistettä, jos $40\,000 < X \le 100\,000$, ja
   • 71 pistettä, jos $X \le 40\,000$.

Esimerkkivuorovaikutus

Tässä on esimerkkisyöte esimerkkitarkastimelle ja sitä vastaavat funktiokutsut.

Syöte 1

5
0 1
0 2
1 3
1 4

Esimerkkikutsut