Klasyczne pytanie: jakie było rozwiązanie wzorcowe do zadania MIN?

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

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.

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").

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

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

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.

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