Fişierul intrare/ieşire: | arhipelag.in, arhipelag.out | Sursă | ONIS 2014, Runda 4 |
Autor | Ionut Bogdanescu | Adăugată de | FMI No Stress •fmins123 |
Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arhipelag
Intr-o seara tarzie, K prieteni au descoperit un joc nou numit Arhipelag. Jocul se desfasoara pe o harta mare pe care se afla mai multe insule, unele fiind legate prin poduri intre ele. Pentru usurinta insulele sunt numerotate de la 1 la N. Un arhipelag este un grup de insule in care se poate ajunge din oricare insula in oricare alta insula folosind podurile existente. Jocul se desfasoara pe runde, in fiecare runda jucatorul aflat la mutare alege un arhipelag pe care-l cucereste. O data ce un arhipelag este cucerit de un jucator, acesta ramane sub controlul jucatorului pana la finalul jocului. Jocul se termina cand nu mai este nici un arhipelag de cucerit. La finalul jocului, toti prietenii sunt curiosi sa afle ce scor are fiecare. Scorul fiecarui jucator este dat de numarul de insule pe care le-a cucerit pe parcursul rundelor. Ordinea jucatorilor este stabilita de comun acord de prieteni si va este data.
Date de intrare
Fişierul de intrare arhipelag.in contine pe prima linie numarul T de teste. Pe prima linie a fiecarui test sunt 3 numere N, M si K, unde N reprezinta numarul de insule, M reprezinta numarul de poduri si K numarul de prieteni. Pe urmatoarele M linii se gaseste cate o pereche de numere intregi care reprezinta 2 insule legate de un pod. Pe ultima linie a unui test se afla ordinea jucatorilor.
Date de ieşire
În fişierul de ieşire arhipelag.out veti afisa in ordine pentru fiecare test cate o linie de forma "Case <t>: <x1> <x2> ... <xK>" (fara ghilimele) unde <t> este numarul testului, iar <x1> este punctajul jucatorului cu numarul 1, <x2> este punctajul jucatorului cu numarul 2, ..., <xK> este punctajul jucatorului cu numarul K.
Restricţii
- T = 5
- 1 ≤ N, M ≤ 100 000
- 1 ≤ K ≤ 100
- Intre 2 insule pot exista mai multe poduri.
Exemplu
arhipelag.in | arhipelag.out |
---|---|
2 5 2 2 1 3 2 4 2 1 11 1 4 9 5 4 2 1 3 | Case 1: 2 3 Case 2: 2 3 2 4 |
Explicaţie
Pentru primul joc jucatorul 2 cucereste arhipelagul format din insula 5, apoi jucatorul 1 ia arhipelagul format din insulele 1 si 3 si la final jucatorul 2 ia arhipelagul format din insulele 2 si 4. La finalul jocului jucatorul 1 are scorul 2 (deoarece detine 2 insule), iar jucatorul 2 are scorul 3 (detine restul de 3 insule).