Editorial for Navios de Azeroth

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Sekai02

Subtarea 1: $n \leq 20$ ~n \leq 20~ (15 puntos):

Para poder obtener los primeros 15 puntos solo bastaba con recorrer todos los nodos a partir de la capital $s$ ~s~ y luego probar todos los posibles subconjuntos de nodos tal que al recorrer las ciudades alcanzables a partir de ellos todos los nodos quedaran visitados. De todos los subconjuntos que cumplan esta condicion nos quedamos con el de tamaño minimo. Esto se podia hacer usando Bitmask y DFS.
Complejidad: $O(2^n*(n+m))$ ~O(2^n*(n+m))~

Subtarea 2: Para cada arista $u_{i} \rightarrow v_{i}$ ~u_{i} \rightarrow v_{i}~ en la entrada se garantiza $u_{i} < v_{i}$ ~u_{i} < v_{i}~ y $n \leq 5000$ ~n \leq 5000~ (20 puntos).

En esta subtarea bastaba con ver cuantos nodos tenian indegree 0 y restar uno a esta cantidad (porque la capital $s$ ~s~ sera uno de estos nodos. Notemos que cualquier nodo $v_{i}$ ~v_{i}~ tal que exista una arista $u_{i} \rightarrow v_{i}$ ~u_{i} \rightarrow v_{i}~ puede ser visitado a partir de $u_{i}$ ~u_{i}~. Ahora notemos tambien que si existe un nodo con indegree 0 no hay manera de llegar a el a partir de otro nodo. Entonces simplemente bastaria con añadir aristas desde $s$ ~s~ hasta estos nodos para poder recorrer toda su componente.
Complejidad: $O(n+m)$ ~O(n+m)~

Subtarea 3: $1 \leq n, m \leq 5000$ ~1 \leq n, m \leq 5000~ (40 puntos).

Se esperaba que la mayoria de los participantes pudieran llegar hasta aqui
Debido a las constraints esta subtarea permite una solución greedy. Recorremos todos los nodos alcanzables a partir de la capital $s$ ~s~ y marquemoslos como nodos buenos, todos los nodos que no fueron marcados llamemosles nodos malos. Ahora vamos a hacer DFS desde todos los nodos malos y contar cuantos nodos malos son alcanzables a partir de cada uno. Sea $bad_{u}$ ~bad_{u}~ la cantidad de nodos malos alcanzables a partir de $u$ ~u~. Ordenemos los nodos malos en pares $bad_{u}, u$ ~bad_{u}, u~ y recorremos en este orden de mayor a menor $bad_{u}$ ~bad_{u}~, cada vez que nos encontramos un nodo $u$ ~u~ que no ha sido visitado sumamos 1 a la respuesta y hacemos DFS marcando los nodos alcanzables. Complejidad: $O(n*m)$ ~O(n*m)~

Subtarea 4: Sin restricciones adicionales (25 puntos).

Para poder obtener todos los puntos en este problema era necesario comprimir las componentes fuertemente conexas del grafo como un solo nodo, contar cuantas tenian indegree 0 y restar uno a esta cantidad porque la componente que contiene a la capital estara entre ellas.
Complejidad: $O(n+m)$ ~O(n+m)~

Para aprender mas acerca del tema:
https://cp-algorithms.com/graph/strongly-connected-components.html

Comments

There are no comments at the moment.