Mam prostsze rozwiązanie niż w opisie.

Swoją drogą w opisie podejrzanie wiele razy jest powtórzona myśl, że zarażenie całej grupy miast jest korzystne ;)

Otóż dzielimy wszystkie dwustronne grupy miast na pół. Jeśli jest nieparzysta liczba miast to środkowe miasto też dzielimy na pół, więc mamy na przykład grupę składającą się z 3.5 miasta.

I teraz wszystkie grupy miast zarażają się z tą samą prędkością, 1 miasto/dzień. Ratujemy grupy od największej. Ja bym powiedział, że dlatego, że ratowanie dużych grup jest korzystne, a nie dlatego, że zarażanie małych grup jest korzystne, no ale to już zależy od punktu widzenia ;)

Sumujemy rozmiary uratowanych grup. Zaokrąglamy w górę do liczby całkowitej, ze względu na to, że jeśli na samym końcu uratowaliśmy pół miasta, to wtedy drugie pół też się załapie na gapę, ale to jedyny wyjątek.