Editorial for Simplemente salta

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: leocar

Simplemente salta:

Subtarea 1:

No se me ocurre nada, pero quizá conocer al next_permutation o simulaciones NP podría ayudar.

Subtarea 2:

Idea $1-O(Q*N^2*log(N))$ ~1-O(Q*N^2*log(N))~: Hacer en cada querie algo parecido al Prim, metemos en una priority_queue pares de $(valor, nodo)$ ~(valor, nodo)~ donde ese valor es una posible respuesta desde el nodo de la querie y el nodo es el nodo. Inicialmente metemos $(oo, Ui)$ ~(oo, Ui)~ o $(oo, Vi)$ ~(oo, Vi)~.

Idea $2-O(Q*N^2)$ ~2-O(Q*N^2)~: Tener las aristas ordenadas y en cada querie hacer un Kruskal en el que paramos cuando $U_i$ ~U_i~ y $V_i$ ~V_i~ estan en la misma componente conexa y la respuesta es la arista que acabamos de poner. Idea $3-O(Q*N+N^2*log(N))$ ~3-O(Q*N+N^2*log(N))~: Hacer un Kruskal(o Prim) y sacar el árbol. En cada querie hacer dfs o bfs para hallar la respuesta.

Subtarea 3:

Idea 1-O(N^2 * log(N)): Hacer un Kruskal(o Prim) y sacar el árbol. Hacer $N$ ~N~ dfs o bfs y hallar la respuesta de todos los pares posibles y guardarlos en una matriz de $N$ ~N~x $N$ ~N~, luego dar cada querie $O(1)$ ~O(1)~.

Comments

There are no comments at the moment.