Caminhos do Reino - F2P1 - OBI 2016

caminhos.cpp

// Caminhos do Reino - F2P1 - OBI 2016
// Rogério Júnior
// Complexidade: O(N+Q)

#include "iostream"
#include "algorithm"
#include "vector"

using namespace std;

#define PB push_back

#define MAXN 100100

int n, q, v, son[MAXN], pos[MAXN], h[MAXN];

bool in_cyc[MAXN];

vector<int> invers[MAXN], cycle;

// função para calcular a distância no ciclo
int mod(int x){
	
	// se x for negativo
	// tenho q dar a volta pelo "outro lado"
	if(x<0) x+=cycle.size();
	
	// e retorno x
	return x;
}

// DFS que calcula o "pai" do vértice no ciclo
// e sua distância dele
void dfs(int v){
	
	// para cada filho de v no grafo inverso
	for(int i=0;i<invers[v].size();i++){
		
		int u=invers[v][i];
		
		// se ele já estiver no ciclo, ignoro
		if(in_cyc[u]) continue;
		
		// se não, ele recebe a posição de v
		pos[u]=pos[v];
		
		// e sua profundidade mais um
		h[u]=h[v]+1;
		
		// e chamo a DFS nele
		dfs(u);
	}
}

int main(){
	
	// leio o valor de N
	cin >> n;
	
	// leio cada aresta
	for(int v=1;v<=n;v++){
		
		int u;
		cin >> u;
		
		// a salvo no grafo direto
		son[v]=u;
		// e no grafo inverso
		invers[u].PB(v);
	}
	
	// percorro os vértices procurando algum no ciclo
	for(int v=1;v<=n;v++){
		
		// se ele tem grau maior que um no cico inverso
		// há dois caminhos que chegam nele, logo ele está no ciclo
		if(invers[v].size()>1){
			
			// o adiciono ao ciclo
			cycle.PB(v);
			in_cyc[v]=true;
			
			// e sigo seu caminho de filhos até completar todo o ciclo
			int u=son[v];
			while(u!=v){
				
				// marco que o cada vértice está no ciclo
				in_cyc[u]=true;
				
				// o adiciono no vetor cycle
				cycle.PB(u);
				
				// e olho o seu filho
				u=son[u];
			}
			
			// quando encontro o ciclo, posso parar o for
			break;
		}
	}
	
	// para cada vértice no ciclo
	for(int i=0;i<cycle.size();i++){
		
		int v=cycle[i];
		
		// salvo sua posição no ciclo
		pos[v]=i;
		
		// e salvo a altura e posição no ciclo
		// de cada vértice do caminho que sai dele
		dfs(v);
	}
	
	// leio o valor de Q
	cin >> q;
	
	for(int i=0;i<q;i++){
		
		// leio os vértices da pergunta
		int a, b;
		cin >> a >> b;
		
		// se os dois estão no mesmo caminho periférico
		// basta imprimir a diferença entre suas alturas
		if(pos[a]==pos[b]) cout << max(h[a]-h[b],h[b]-h[a]) <<" \n"; 
		
		// se não
		else{
			
			// calculo o tempo para que se encontrem no pai de A e de B
			int da, db;
			
			da=max(h[a],h[b]+mod(pos[a]-pos[b]));
			db=max(h[b],h[a]+mod(pos[b]-pos[a]));
			
			// e imprimo o menor deles
			cout << min(da,db) << "\n";
		}
	}
	
	// por fim, retorno zero
	return 0;
}