Zadanie tygodnia
Runda 0; kategoria Hard
Limit czasowy: 2s; Limit pamięciowy: 128MB
Jest burzliwa jesień na dalekiej prowincji. Baytard, syn lokalnego bankiera i znany awanturnik kupił właśnie nowy samochód wyścigowy. Zamierza jeździć nim po okolicznych miastach. Lokalne miejscowości połączone są siecią dróg. Drogi są dwukierunkowe. Baytard gardzi jeżdżeniem po bezpiecznych ulicach. Pragnie podróżować jedynie niebezpiecznymi ścieżkami. Jak one wyglądają? Otóż Baytard stwierdził, że najwięcej emocji sprawi mu podróż po drogach, na których wypadek byłby naprawdę spektakularny. Powiemy, że droga między dwoma miastami jest niebezpieczna jeśli wypadek na niej (czyli zablokowanie tej drogi) sprawiłby, że po sieci lokalnych dróg nie dałoby się przejechać (przez pośrednie miejscowości) pomiędzy parą miast, połączonych zablokowaną drogą.
Niebezpieczna ścieżka to ścieżka prosta (bez powtarzających się krawędzi), która składa się wyłącznie z niebezpiecznych dróg. Ponadto Baytard, nie chcąc być oskarżonym o tchórzostwo, chce wybrać taką ścieżkę, której nie dałoby się przedłużyć w żadną ze stron o kolejną niebezpieczną drogę. Na ile sposobów może wybrać taką niebezpieczną ścieżkę?
Wejście:
Pierwsza linia wejścia zawiera dwie liczby i , oznaczające kolejno liczbę miast i liczbę dwukierunkowych dróg między nimi (, ). W kolejnych liniach znajdują się pary liczb naturalnych i oznaczające, że miasta o numerach i są połączone drogą. Żadna para nie pojawi się na wejściu więcej niż raz.
Wyjście:
Jedyna linia wyjścia powinna zawierać jedną liczbę całkowitą - liczbę nieprzedłużalnych niebezpiecznych ścieżek.
Przykład 1:
Wejście:
Wyjście:
2
Przykład 2:
Wejście:
Wyjście:
3
Na poniższych rysunku na czerwono są zaznaczone nieprzedłużalne niebezpieczne ścieżki dla obu przykładów (dla pierwszego 1-5 oraz 2-6, dla drugiego 2-1-3, 2-1-4, 3-1-4):
Pozycja | Imię i nazwisko | Wynik | Czas |
---|---|---|---|
1 | Przemek Komosa [1] | 10 | 132:40:15 |
2 | Szymon Stankiewicz [2] | 10 | 133:56:48 |
3 | Adam Czapliński [3] | 10 | 157:00:02 |
4 | Przemysław Derengowski [4] | 10 | 185:36:43 |
5 | Jakub Sygnowski [5] | 10 | 249:40:39 |
6 | Wojciech Żółtowski [6] | 10 | 612:26:32 |
7 | Witold Długosz [7] | 10 | 2775:48:15 |
8 | Bartek Dudek [8] | 2 | 159:41:03 |
9 | Michał Kiełbowicz [9] | 1 | 148:16:54 |
Odnośniki:
[1] http://informatyka.wroc.pl/user/2060
[2] http://informatyka.wroc.pl/user/429
[3] http://informatyka.wroc.pl/user/531
[4] http://informatyka.wroc.pl/user/462
[5] http://informatyka.wroc.pl/user/365
[6] http://informatyka.wroc.pl/user/2190
[7] http://informatyka.wroc.pl/user/2175
[8] http://informatyka.wroc.pl/user/334
[9] http://informatyka.wroc.pl/user/614
[10] http://informatyka.wroc.pl/user
[11] http://informatyka.wroc.pl/user/register