Logowanie

Zadanie Narciarze OI

pytanie zadane 22 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/Yb04CMWb5dkJbro4Hhmexx_E/site/?key=statement
Myślałem, żeby póścić BFS-a od jedynki, żeby uporządkować je w kolejności, gdy w momencie przetwarzania wierzchołka x, mam przetwożonych wszystkich jego poprzedników, ale to chyba nie zadziała.

Z góry dziękuję za pomoc i poświęcony czas!

komentarz 22 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Już wkleiłem dobry link do zadania.

komentarz 22 marca 2023 przez Whistleroosh Maniak (56,980 p.)

brzmi jak przepływy

komentarz 22 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

o ja dziękuję xD

komentarz 22 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@Whistleroosh,

Trudne te przepływy?

komentarz 22 marca 2023 przez Whistleroosh Maniak (56,980 p.)

Nie trudniejsze niż FFT :) Ale na OI raczej nie potrzeba znać przepływów

komentarz 22 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Przepływy to o to chodzi: https://www.youtube.com/watch?v=LZtY26VDJDg ?

komentarz 22 marca 2023 przez Whistleroosh Maniak (56,980 p.)

Tak

komentarz 23 marca 2023 przez Whistleroosh Maniak (56,980 p.)

Spojrzałem jeszcze raz na treść i pominelismy ważną kwestię. Ten graf jest planarny

komentarz 23 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Chyba zachłan wejdzie, gdzie będę szedł DFS-em najbardziej lewą ścieżką. Ale nie mam dowodu

komentarz 23 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Bo te przepływy to o ile dobrze rozumiem, to mają O(N^3), czyli zawolno. jak N <= 5000 w tym zadaniu.

komentarz 23 marca 2023 przez Whistleroosh Maniak (56,980 p.)

Zachłan wejdzie. Gdyby graf nie był planarny to by nie zadziałało

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów

1 odpowiedź 219 wizyt

Zadanie żywopłot, finał XXIII OI

pytanie zadane 13 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

0 głosów

1 odpowiedź 574 wizyt

Zadanie Midas finał XXIV OI

pytanie zadane 7 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

0 głosów

1 odpowiedź 156 wizyt

Zadanie Cło 1 etap XV OI

pytanie zadane 20 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...