Szybka ankieta:

-Jeśli masz 10 punktów i złożoność O(n^3), to poproszę łapkę w górę.
-Jeśli masz 10 punktów i złożoność O(n^4/64), to poproszę łapkę w dół.
-W pozostałych przypadkach proszę o zignorowanie.

O(n^4logn/64) też wchodziło na 10

Czy specjalnie pominąłeś logi? Jak to się robi w O(n^3)?

Ja mam O(n^4) bez "/64" ale z innymi optymalizacjami.

Przede wszystkim na samym początku obliczamy w O(n^3) odległości między wszystkimi parami wierzchołków.

Teraz iterujemy się po możliwych parach miejsc na teleporty i utrzymujemy globalną zmienną na wynik (na początku n). Będziemy potrzebować funkcji check(a, b, x), która sprawdza, czy gdy w wierzchołkach a oraz b damy teleporty, to wynik będzie <=x. Iterując się po tych parach zawsze próbujemy odpalać check(a, b, wynik-1) i dopóki da się go zmniejszyć to zmniejaszamy. W ten sposób funkcję check() odpalimy O(n^2) razy.

Pytanie jak powinna działać nasza funkcja check(a, b, x). Iterujemy się po v i bez straty ogólności zakładamy, że v ma bliżej do a niż do b. To co chcemy sprawdzić, to czy wszystkie wierzchołki odległe od v o ponad x są odległe od b o co najwyżej x-odl(v, a) (ponieważ to do tych wierzchołków musielibyśmy dojść teleportując się z a do b). Tutaj możemy skorzystać z tego, że zapytania zadajemy w kolejności malejącej po x i utrzymywać tablicę najdalszy[v][b], która spośród wszystkich wierzchołków u takich, że odl(v, u)>x, pamięta największą odległość od b do któregokolwiek z nich. Za każdym razem gdy dla x musimy wrzucić do struktury jakąś parę (v, u), to po prostu iterujemy się po b i maxujemy najdalszy[v][b] z odl(b, u). Funkcja check(a, b, x) będzie liniowa, sumaryczna aktualizacja najdalszy[v][b] zajmie O(n^3) i całość również zamknie się w O(n^3).

Jeżeli n^4 log n / 64 wchodziło to kiepsko ze strony opracowujących
Napomknę, że z teoretycznego punktu widzenia ta złożoność to dokładnie to samo co O(n^4), czyli najgorszy brut. W praktyce nie powinny być zbyt odległe też
O(n^4) "z innymi optymalizacjamo" na 10 pkt też mnie niezbyt cieszy
Ale no trudne zadanie do układania testów. Przez swoje n godzin rozkminy wymyśliłem dużo hereł czasowych i myślałem że opracowujący mieliby trudne zadanie je powycinać. Widzę, że się sprawdziło xd

Ja też mam 10 za rozwiązanie O(n^4) (max czas 1s), które dla każdego teleporta iteruje się po wszystkich parach wierzchołków, posortowanych malejąco po ich odległości i robi brake gdy tylko można już określić średnicę - ten opt w pojedynkę wystarczał. Mam test* który na uruchomieniu próbnym działa w >3s, i dlatego koniec końców wysłałem O(n^4/w) na bitsetach. Chodzi w 0.3s, mimo że na uruchomieniu próbnym na cyklu długości 399 chodzi ponad 1s.

*krzyż gdzie każde ramie ma n/6 wierzchołków + do dwóch ramion doczepione po n/6 wierzchołków

Może lepiej byłoby poprosić o obliczenie średnicy dla każdej pary. Mam rozwiązanie w O(n^3) (które działa wolniej niż O(n^3 * log(n)) xd)

O(n^3 log n / 64)

Mój piękny brucik o(n^4), lecz z m.in. losowaniem i konczeniem wczesniej, wchodzi na (aż) 10pkt. Końcowo o(n^3logn)

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.