• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

zadania Randka OI

Object Storage Arubacloud
0 głosów
127 wizyt
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ź

+2 głosów
odpowiedź 24 czerwca 2023 przez Whistleroosh Maniak (56,980 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 (56,980 p.)
Tak, ta obserwacja wystarczy do rozwiązania zadania
1
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.

Podobne pytania

0 głosów
1 odpowiedź 215 wizyt
pytanie zadane 13 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 550 wizyt
pytanie zadane 7 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
0 odpowiedzi 266 wizyt
pytanie zadane 22 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,538 zapytań

141,380 odpowiedzi

319,461 komentarzy

61,926 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

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!

...