Zawody stałe, runda 4
Limit czasowy : 1s ; Limit pamięciowy: 32 MB
W Górach Kaczawskich znaleziono niedawno bogate złoża. Na szczęście nie chodzi o węgiel brunatny - tym razem to diamenty, ukryte w twardej skale. Badacze odkryli w okolicach złoża system podziemnych tuneli, naturalnego pochodzenia. Chcą pobrać próbki diamentów, aby zadecydować, czy warto eksploatować złoże. Zrozumiałym jest, że chcą znaleźć jak najwięcej kamieni. Sieć tuneli zaczyna się od wejścia - jaskini - i składa się z podziemnych grot, połączonych korytarzami. Każdy korytarz prowadzi zawsze do groty znajdującej się niżej, niemożliwy jest więc powrót do groty, z której się przybyło. Z jednej groty może prowadzić w dół dowolna liczba tuneli, może nie prowadzić też żaden. Każde dwie groty są połączone co najwyżej jednym bezpośrednim tunelem. Tunele nie przecinają się, ale mogą biec pod lub nad sobą. Groty oznaczono kolejnymi liczbami naturalnymi, jaskinia zaś posiada numer 0. W każdej z grot znajduje się nieujemna liczba diamentów. Badacze dysponują niewielkimi środkami i chcieliby zejść tunelami tylko raz, na dowolną głębokość. Znając plan tuneli i ilość diamentów w każdej z grot, pomóż im obliczyć, ile najwięcej diamentów do badań mogą zebrać.
Zadanie:
Dla danego planu połączeń pomiędzy grotami w kopalni, Twój program powinien podać największą możliwą liczbę diamentów, które można zebrać na dowolnej trasie w głąb systemu tuneli, gdy startuje się z jaskini. Twój program powinien wczytywać dane na standardowe wejście i wypisywać odpowiedź na standardowe wyjście.
Wejście:
W pierwszej linii wejścia znajdują się dwie liczby całkowite n i m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000), oznaczające kolejno ilość grot i ilość tuneli. W następnej linii znajduje się n liczb ci (0 ≤ ci ≤ 1 000), oznaczających ilość diamentów w i-tej grocie. W kolejnych m liniach znajdują się pary liczb aj bj (0 ≤ aj ≤ n, 0 < bj ≤ n) oznaczające numery grot stanowiących początek i koniec j-tego tunelu.
Wyjście:
Wyjście powinno składać się z jednej liczby - największej liczby diamentów możliwej do zebrania.
Przykład
Wejście:
7 10
0 7 3 0 2 4 8
0 2
0 3
4 6
0 6
6 5
7 1
6 1
2 7
3 2
3 5
Wyjście:
18
ścieżka od jaskini, przez groty 3, 2, 7, 1.
Pozycja | Imię i nazwisko | Wynik | Czas |
---|---|---|---|
1 | Maciej Szeptuch [3] | 10 | 11:44:20 |
2 | Anna Piekarska [4] | 10 | 15:38:04 |
3 | Wojciech Kuprianowicz [5] | 10 | 55:29:45 |
4 | Karol Kontny [6] | 10 | 60:01:59 |
5 | Darek Bukowski [7] | 10 | 108:23:58 |
6 | Bartek Dudek [8] | 10 | 137:10:42 |
7 | Piotr Strzelecki [9] | 10 | 346:38:10 |
8 | Krzysztof Story [10] | 10 | 346:46:22 |
9 | My My [11] | 10 | 752:46:24 |
10 | Mateusz Wasilewski [12] | 10 | 944:19:28 |
11 | Piotr Jagiełło [13] | 10 | 1620:40:42 |
12 | Przemysław Derengowski [14] | 10 | 1932:35:57 |
13 | Michal Zgliczynski [15] | 10 | 2359:59:43 |
14 | Janusz Wróbel [16] | 10 | 2455:18:53 |
15 | Kamil Łukasz [17] | 10 | 3968:59:59 |
16 | Maciej Kisiel [18] | 10 | 6074:38:25 |
17 | Michał Karpiński [19] | 10 | 8215:38:06 |
18 | Szymon Stankiewicz [20] | 10 | 8704:51:10 |
19 | Kuba Skałecki [21] | 10 | 8718:39:28 |
20 | Jakub Oćwieja [22] | 10 | 9273:20:44 |
21 | Łukasz Hanuszczak [23] | 10 | 10592:08:40 |
22 | Kamil Dębowski [24] | 10 | 11801:06:32 |
23 | Karol Farbiś [25] | 10 | 11963:41:52 |
24 | Rafał Wójcik [26] | 10 | 11965:34:02 |
25 | Witold Długosz [27] | 10 | 13313:11:11 |
26 | Agnieszka Dudek [28] | 9 | 153:25:14 |
27 | Jadwiga Andryszak [29] | 9 | 182:54:28 |
28 | Łukasz Hryniuk [30] | 9 | 8632:27:38 |
29 | Marek Hołyński [31] | 9 | 9053:00:19 |
30 | Rafał Cieślak [32] | 8 | 877:10:13 |
31 | Marcin Skiba [33] | 8 | 4744:18:52 |
32 | Przemysław Wawrzyniak [34] | 4 | 12460:34:47 |
33 | Kuba Skudlarski [35] | 2 | 87:25:51 |
Odnośniki:
[1] http://informatyka.wroc.pl/user
[2] http://informatyka.wroc.pl/user/register
[3] http://informatyka.wroc.pl/user/113
[4] http://informatyka.wroc.pl/user/203
[5] http://informatyka.wroc.pl/user/172
[6] http://informatyka.wroc.pl/user/130
[7] http://informatyka.wroc.pl/user/148
[8] http://informatyka.wroc.pl/user/334
[9] http://informatyka.wroc.pl/user/135
[10] http://informatyka.wroc.pl/user/139
[11] http://informatyka.wroc.pl/user/402
[12] http://informatyka.wroc.pl/user/652
[13] http://informatyka.wroc.pl/user/112
[14] http://informatyka.wroc.pl/user/462
[15] http://informatyka.wroc.pl/user/545
[16] http://informatyka.wroc.pl/user/155
[17] http://informatyka.wroc.pl/user/549
[18] http://informatyka.wroc.pl/user/792
[19] http://informatyka.wroc.pl/user/387
[20] http://informatyka.wroc.pl/user/429
[21] http://informatyka.wroc.pl/user/1682
[22] http://informatyka.wroc.pl/user/2026
[23] http://informatyka.wroc.pl/user/126
[24] http://informatyka.wroc.pl/user/1845
[25] http://informatyka.wroc.pl/user/1020
[26] http://informatyka.wroc.pl/user/2486
[27] http://informatyka.wroc.pl/user/2175
[28] http://informatyka.wroc.pl/user/142
[29] http://informatyka.wroc.pl/user/351
[30] http://informatyka.wroc.pl/user/341
[31] http://informatyka.wroc.pl/user/1581
[32] http://informatyka.wroc.pl/user/123
[33] http://informatyka.wroc.pl/user/819
[34] http://informatyka.wroc.pl/user/2162
[35] http://informatyka.wroc.pl/user/128