Jak kilka osób z czołówki jest zgodna, to myślę że można im wierzyć. A co do równości, to niepotwierdzenie jest bardziej wiarygodne (ale rzadsze), bo wtedy przeważnie ludzie piszą gdzie są błędy, przez co łatwiej wykryć zgodność lub ściemę.

Natomiast bardziej bym się obawiał że takie testy nie pokrywają wszystkich sytuacji brzegowych.

O prosze, tez zrobilem taki graf, ale jako bruta, nie wpadlem na to ze da sie go dooptymalizowac. Dziekuje za odpowiedzi i jestem ciekawy czy w takim razie ktos mial faktyczna wzorcowkw

Judges measure real time, they’re simply slow in a specific way.

Rozwiązanie wzorcowe ma złożoność O(n*log^2(n)). Postaramy się sporządzić dokument z rozwiązaniami taki jak rok temu.

Did the same including the pruning. I think it runs in <4s, but it gets MLE 3/10 :( very hard to predict non-real-time judges

Niby mam 10/10, ale w sumie to czasy mam gorsze niż się spodziewałem. Mam max czas 6.73 i chyba kluczowy był opt, że ifuję że jak z danej SSS nie jestem w stanie nic osiągnąć to nie do-orowuję jej maski

Ja to samo, i mam test gdzie dostaję DAG o 538k wierzchołkach i 2.2M krawędziach; na test runie działało mi 6.5s po grubym żyłowaniu... natomiast na oficjalnych testach mam max czas 3.8s (?).

> nie ma bata aby ten graf po skompresowaniu do SSS miał duży rozmiar

Max teoretyczny dla n = 10^5 to chyba coś rzędu 1.5M wierzchołków, ja na moim teście mam 0.5M, więc chyba ten graf asymptotycznie jest wciąż rozmiaru O(n log n), tylko z małą stałą. No chyba że wy go jakoś lepiej postprocessujecie (ja musiałem np. uważać żeby dokladać tylko wierzchołki które są "istotne").

8

Jaki wam wychodzi wynik dla
5
2 2 3
2 3 4
2 4 5
1 5
0

?

Pionek = Król ∖ Goniec

I zauważę, że pionki wcale nie chodzą jak królowie w szachach, tzn. nie mogą chodzić po skosie

Ahh, no tak. Standardowo zaćmienie :P Dzięki

Może.
Ale nie da się tej pozycji osiągnąć po (dokładnie) 100^100^100^100 ruchach.

Może jestem głupi, ale totalnie nie rozumiem, czemu jest tam 0. Pionki chodzą tu jak królowie w szachach, więc czemu ten dolny nie może wejść na górę, żeby osiągnąć docelową pozycję? Chyba nie muszą ruszać się jednocześnie?

Identycznie jak Wojtek. Najgorszy test jaki mi się udało zrobić miał w DAGu miał jakieś 250k wierzchołków i 1.3mln krawędzi, ale w robienie testów najlepszy to nie jestem. Na sio2 śmigało na nim w 3.5s.
edit: Dostało 10/10.

Wzorcówki nie znam, ale znam swoje rozw w O(n^2 log n / 64), które sądzę, że jest bardzo duża szansa, że dostanie 10/10.

W skrócie, wyznaczam graf skierowany wielkości O(n log n) taki że dla i, j<=n z v_i do v_j da się dojść iff po wybuchnięciu miny i, wybucha także mina j (być może pośrednio). To znaczy reachability w tym grafie mi odpowiada odpowiedziom. Następnie liczę reachability na tym grafie poprzez bitsety.

Ten graf tworzę tak, że biorę sobie centroid i sortuję wierzchołki po odległości od niego. Jak wierzchołek v spełnia r[v]>=dis[v] (dis to odległość do centroiu), to wybuchnięcie miny v bezpośrednio wybucha wszystkie miny w odległości <=r[v]-dis[v] od centroidu, tzn. jakiś prefiks tej posortowanej listy. Jak sobie potworzę sztuczne wierzchołki na prefiksy, to łatwo zamodelować wszystkie takie przejścia dodając O(n) wierzchołków i krawędzi

Rozwiązanie bardzo śmiga, bo nie ma bata aby ten graf po skompresowaniu do SSS miał duży rozmiar