Runda 2 - Przychodnia

28.09.2009 - Damian Rusak
TrudnośćTrudność

Zawody stałe, runda 2

Limit czasowy: 3s; Limit pamięciowy: 64 MB

 


Przychodnia


Stało się! Wymiarowa grypa zaatakowała i Wymiarlaki popędziły masowo do przychodni, aby przebadać się i zaaplikować sobie szczepionkę, reklamowaną jako niezawodna. Utworzyła się długa kolejka do gabinetu lekarskiego i jak to w kolejce bywa, wytworzyły się spięcia społeczne. Wymiarlaki to bardzo spokojne stworzenia, nie manifestują więc swojej wrogości, tylko przyjaźń. Udało Ci się zauważyć, że wiele z nich publicznie okazuje sobie w kolejce życzliwość. Co więcej, zgodnie z zasadą „przyjaciel mojego przyjaciela jest moim przyjacielem”, każdy Wymiarlak odczuwa przyjaźń w stosunku do samego siebie i do każdego przyjaciela swoich przyjaciół. W ten sposób można podzielić Wymiarlaki w kolejce na grupy towarzyskie w ten sposób, że każde dwa Wymiarlaki w danej grupie łączy przyjaźń (być może nie bezpośrednio, ale przez kilku przyjaciół). Wymiarlaki są bardzo wrażliwe i solidarne - każda grupa przyjaciół przepuści w kolejce swojego najmniej odpornego na grypę członka. Ponieważ bardzo Cię ciekawi, kto przyjaźni się z kim, napisz program, który odkryje relacje między oczekującymi Wymiarlakami.


Zadanie:


Znając okazywane publicznie oznaki przyjaźni, regułę „przyjaciel mojego przyjaciela jest moim przyjacielem” oraz odporność każdego Wymiarlaka, napisz program, który wypisze  numery najmniej odpornych na grypę osobników z każdej grupy.


Wejście:


Pierwsza linia wejścia zawiera dwie liczby n i m, (1 ≤ n ≤ 500000, 1 ≤ m ≤ 500000) oznaczające kolejno ilość Wymiarlaków w kolejce i ilość par Wymiarlaków, publicznie okazujących przyjaźń. W kolejnej linii znajduje się n liczb całkowitych ci (1 ≤ ci ≤ 1000) oznaczających odporność kolejnych Wymiarlaków, począwszy od pierwszego. W następnych m liniach znajdują się pary liczb całkowitych aj bj (1 ≤ aj < bj ≤ n), oznaczające, że Wymiarlaki o numerach aj oraz bj okazują sobie publicznie przyjaźń. Może się zdarzyć, że niektóre pary pojawią się wielokrotnie na wejściu.


Wyjście:


W pierwszej linii wyjścia powinna znaleźć się jedna liczba - ilość rozłącznych grup towarzyskich. W następnych liniach należy wypisać, w kolejności rosnących numerów, numery członków różnych grup, po jednym o najmniejszej odporności na grypę z każdej grupy.  Jeśli kilku członków jednej grupy ma tę samą, najmniejszą odporność, należy wypisać tego o najmniejszym numerze.


Przykład:

Wejście:

8 9
3 5 8 2 5 7 1 14
1 7
3 6
5 8
2 5
2 8
2 5
1 6
4 6
6 7


Wyjście:

2
2
7

 

Jedna z grup towarzystkich to {1,3,4,6,7}, druga {2,5,8}. W pierwszej z nich najmniejszą odporność (1) ma Wymiarlak numer 7, w drugiej Wymiarlaki 5 i 2 mają odporność 5 - wybierany jest Wymiarlak nr 2. Liczby 7 i 2 pososrtowane malejąco dają ciąg 2, 7.

Zapraszamy do dyskusji na temat zadania na forum.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Zgłoś problem z systemem sprawdzania zadań(problem z wysłaniem programu, obejrzeniem kodu źródłowego itp).

PozycjaImię i nazwiskoWynikCzas
1Kuba Skudlarski1010:58:19
2Wojciech Kuprianowicz1012:55:50
3Bartek Dudek10111:07:40
4Darek Bukowski10136:43:17
5Maciej Szeptuch10149:55:01
6Piotr Jagiełło10178:20:10
7Piotr Strzelecki10178:33:43
8Krzysztof Story10346:28:41
9Jadwiga Andryszak10401:47:35
10Piotr Kosecki101016:05:58
11Marcin Pilecki101289:18:06
12Mateusz Wasilewski101356:35:06
13Marcin Witczak101454:06:46
14Paweł Piotrowski101482:00:12
15Grzegorz Milka101561:04:36
16Łukasz Hanuszczak102000:40:39
17Przemysław Derengowski102263:11:48
18Michal Zgliczynski102695:36:01
19Janusz Wróbel102790:51:56
20Tomasz Wiatrowski102793:18:59
21Maciej Poleski103652:10:36
22Adam Żychowski103707:28:55
23Anna Piekarska104264:24:51
24Kamil Łukasz104302:06:41
25Łukasz Budkowski104358:43:29
26Krzysztof Jamróz105114:02:28
27Maciej Kisiel106390:27:11
28Piotr Szefler107456:50:52
29Michał Karpiński108550:04:25
30Szymon Stankiewicz108868:47:47
31Kuba Skałecki109060:28:36
32Marek Hołyński109367:08:15
33Jakub Oćwieja109591:09:25
34Michał Zezyk1012081:57:43
35Kamil Dębowski1012134:58:17
36Agnieszka Dudek7178:35:38
37Wojciech Kubies684:14:05
38Franciszek Okrzesik61883:54:21
39Krzysztof Cirocki57379:27:17
40Marcin Grzywaczewski3180:13:33
41Karol Kontny2179:00:20
42Adam Laskowski21648:48:32
43Łukasz Hryniuk23875:16:35
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com