Potwierdzam wszystko

Potwierdzam.

Wszystkie testy są wyśmienite, polecam

Potwierdzam wszystko

Potwierdzam

Potwierdzam

Nie potwierdzam, ale mam kolegę, który też nie potwierdza.

Potwierdzam

Potwierdzam

Potwierdzam paczke filipa, plik z outem filipa do testu 274 to 0.9999715.

Potwierdzam całość drugiego załączonego pakietu, chociaż w przypadku outów Filipa mam problem (z precyzja?) – tzn. uruchomiłem brute-force dla testu 274 i otrzymałem "0.9999715", podczas gdy outy wskazują "0.9999886". Czy ktoś inny mógłby to sprawdzić :))?

EDIT: Chyba sprawdzałem zły plik? teraz jest ok, przepraszam.
EDIT 2: Teraz również potwierdzam outy Filipa.

Potwierdzam

Potwierdzam

Moje rozwiązanie jest chyba równoważne temu, co zrobił Mateusz, ale patrzę się na to z trochę innej strony.

Tak samo przechodzimy po każdej krawędzi (v, u) i sprawdzamy, jaka będzie średnica po jej dodaniu. Jeżeli potrafimy odpowiadać w czasie stałym na zapytania max_dist(s, v, u) -> jaka jest maksymalna odległość od s po dodaniu (v, u), to wystarczy się przejść po wszystkich s i wziąć maksimum.

Bez straty ogólności interesują nas tylko takie zapytania max_dist(s, v, u) gdzie dist[s][v] < dist[s][u]. Zauważmy, że nie interesuje nas jakie dokładnie jest v, tylko ile wynosi dist[s][v]. Możemy rozważać trochę inne zapytania max_dist2(s, d, u) gdzie wiemy, że dist[s][v] = d.

Dla każdej pary (s, u) zrobimy strukturkę która odpowiada na zapytania max_dist2. Popatrzmy się na to, jak odległość od danego k się zmienia wraz z zmianą d. Wykres tej odległości to taki daszek. Chcemy umieć obliczyć dla każdego d maxa z wartości daszków dla wszystkich k w punkcie d. Możemy to zrobić liniowo analogicznie do np liczenia maksów sufiksowych.

Potwierdzam