Czy ktoś podzieliłby się rozwiązaniem do ALC? Ja zrobiłem w O(nm), ale to starczyło tylko na 4/10. Pewnie mógłbym żyłować stałą, ale podejrzewam, że brakuje mi jakiejś ostatniej obserwacji. Robiłem tak:

1. Szukamy jakiegoś wspólnego nadgrafu danych grafów, rozwiązanie to będzie zbiór krawędzi dodanych do pierwszego grafu (A) z plusem, i zbiór krawędzi dodanych do drugiego grafu (B) z minusem, w odwrotnej kolejności.
2. Żeby znaleźć ten nadgraf, biorę krawędzie B - A, i dla każdego wierzchołka X odpalam bfs, szukając alternatywnej ścieżki do wierzchołków Y, takich, że X-Y jest w B - A. Kiedy znajdę taką ścieżkę X, x_1, ... x_k, Y, to mogę dodać połączenia X - x_2, X - x_3, ..., X - Y.
3. (B - A) + te ekstra krawędzie + ekstra krawędzie z procesu dla (A - B) to wszystkie krawędzie, które trzeba dodać.

Graf ma co najwyżej 30k wierzchołków / 50k krawędzi, co przy limicie 200k ruchów daje niezły zapas.
Żeby móc modyfikować krawędzie, potrzebujemy żeby istniał atom sąsiadujący z obydwoma jej końcami... To może utwórzmy atom, który sąsiaduje ze wszystkimi innymi?

Więc przyjmując że atom #1 to root:
1) odpalam BFS na pierwszym grafie, startując od roota i w tej kolejności dodaję połączenia do/z roota (jeśli nie istnieją);
2) dodaję w dowolnej kolejności pozostałe krawędzie, których brakuje (już mogę, bo wszystko jest połączone z rootem);
3) usuwam w dowolnej kolejności krawędzie nie prowadzące do/z roota;
4) odpalam BFS na docelowym grafie i w odwrotnej kolejności (od najdalszych wierzchołków) usuwam krawędzie do/z roota, których być nie powinno;

Maksymalne oszacowanie liczby ruchów to:
1) 30k operacji
2) 50k operacji
3) 50k operacji
4) 30k operacji
co spokojnie mieści się w limicie

Może i przekombinowane, ale wystarczyło na 10/10.

Można też w ogóle najpierw przeprowadzić pierwszy graf na gwiazdę bez dodatkowych krawędzi (czyli np. 1 połączone ze wszystkim i całą resztę usunąć), a potem tę gwiazdę na docelowy graf - być może trochę łatwiej o tym myśleć, bo graf "pośredni" zależy tylko od liczby wierzchołków, a maksymalna liczba kroków jest taka sama.

Ponadto pomocny do wykminienia/implementacji może okazać się fakt, że ruchy są swoimi wzajemnymi "odwrotnościami", więc przeprowadzenie grafu pośredniego na końcowy to to samo, co przeprowadzenie końcowego na pośredni, tylko "puszczone od tyłu" i z zamienionymi plusami-minusami.

Robię tak samo jak @Krzysztof Krawczyk (:
Tylko zamiast bawić się z bfs'em, korzystam z tego, że dobrą kolejnością będzie:

(1) preorder dfs od jedynki
(2) dowolna kolejność
(3) dowolna kolejność
(2) postorder dfs od jedynki

Także dwa trywialne dfs'y i dwa fory.