Автор задачи: Даниил Голов, разработчик: Константин Бац
Заметим, что если изначально есть тоннель из хотя бы одной локации с Алиотом в локацию $$$n$$$, то герои не смогут от него спастись, так как при любом маршруте движения героев они окажутся в локации $$$n$$$ либо позже, либо одновременно со своим врагом. С другой стороны, если нет ни одного тоннеля от локации с Алиотом в локацию $$$n$$$, то герои всегда могут спастись, так как можно построить тоннель $$$1 \leftrightarrow n$$$ (если он еще не построен) и добраться до убежища первыми.
С учетом предыдущих замечаний, можно построить тоннели между всеми парами локаций, кроме пар локаций $$$a_i \leftrightarrow n$$$. Всего может быть $$$\dfrac{n \cdot (n - 1)}{2}$$$ тоннелей, из них $$$k$$$ тоннелей построить нельзя (именно в стольких локациях уже есть Алиот), а $$$m$$$ тоннелей уже построено. Поэтому, если герои могут спастись, то дополнительно можно построить $$$\dfrac{n \cdot (n - 1)}{2} - k - m$$$ тоннелей.
Таким образом в решении было достаточно проверить, существует тоннель, связывающий какой-нибудь $$$a_i$$$ и $$$n$$$. Если такой тоннель есть, то ответ равен $$$-1$$$. Иначе ответ на задачу — $$$\dfrac{n \cdot (n - 1)}{2} - k - m$$$.
Для хранения и быстрой проверки, находится ли Алиот в тоннеле $$$j$$$ (то есть есть ли такой $$$i$$$, что $$$a_i = j$$$), можно вместо списка $$$a_i$$$ хранить массив значений $$$\mathtt{marks}$$$, где $$$\mathtt{marks}[i] = 1$$$, если в локации $$$i$$$ есть Алиот, и $$$\mathtt{marks}[i] = 0$$$ иначе.
Тогда асимптотика такого решения будет равна $$$\mathcal{O}(n + m)$$$.