Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
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.
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.
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