Logowanie

zadania Randka OI

pytanie zadane 23 czerwca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Uczę się o LCA i natknąłem się na takie zadanie: link ,które rzekomo da się zrobić za pomocą LCA. Przybruciłem jakiegoś DFS-a / BFS-a na 40pkt, no i to wsm tyle co mu się udało wymyśleć. Kompletnie nie widzę jak zrobić szybciej. Nie widzę też jak skorzystać z LCA w tym zadaniu, chociaż max / min na ścieżce jest charakterystyczny dla tych jump pointerów. Poprosiłbym o hinta.

Z góry dzięki.

1 odpowiedź

odpowiedź 24 czerwca 2023 przez Whistleroosh Maniak (57,400 p.)
wybrane 29 listopada 2023 przez pasjonat_algorytmiki

Najlepsza

Graf w którym z każdego wierzchołka wychodzi dokładnie jedna krawędź ma ciekawe własności. Jakie?

1	komentarz 24 czerwca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.) Można go podzielić na drzewa tak jak w tym zadaniu skarbonki z OI i już wsm coraz bliżej do LCA.

1	komentarz 24 czerwca 2023 przez Whistleroosh Maniak (57,400 p.) Tak, ta obserwacja wystarczy do rozwiązania zadania

komentarz 29 listopada 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Tak faktycznie jest to prawda. Nie wiem czemu wtedy nie umiałem tego zrobić, ale faktycznie dzielimy ten nasz graf strzałkowy na takie właśnie cykle, do każdego mogą wchodzić jakieś krawędzie i powstają nam takie tak jakby drzewa i jump pointerami sprawdzamy czy da się dojść z a do b / do cyklu, jak do cyklu to tam wzorkiem na cyklu liczymy wynik. I wchodzi na 100pkt.