Fişierul intrare/ieşire:arhipelag.in, arhipelag.outSursăONIS 2014, Runda 4
AutorIonut BogdanescuAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inarhipelag.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content