Solução Túneis Subterrâneos

Solução por Lucca Siaudzionis

Este problema é um problema básico se for resolvido pelo algoritmo do Mínimo Ancestral Comum (LCA - Lowest Common Ancestor). Há duas maneiras típicas de fazer, uma em O(n \ lg n) e outra em O(n \ \sqrt{n} ). Você pode aprender a fazer o o LCA em O(n \ \log{n}) na nossa aula do Curso Noic de Informática, clicando aqui. Além disso, um material que explica (em português!) muito bem o LCA em O(n \ \sqrt{n}) pode ser visto neste link.

Seguindo o mesmo estilo que se faz no material, o código fica assim:


#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;
//----------------------
#define MAXN 100100
typedef long long lint;
int n;
lint dist[MAXN]; //distancia pro 0
bool visited[MAXN];
vector<int> grafo[MAXN];
int segmento;
int pai[MAXN];
int nivel[MAXN];
int super_pai[MAXN];
//----------------------
void monta_super_pai(int x, int p){
visited[x] = 1;
super_pai[x] = p;
if(nivel[x] % segmento == x) p = x;
for(int i = 0;i < grafo[x].size();i++)
if(!visited[grafo[x][i]])
monta_super_pai(grafo[x][i], p);
}
int lca(int a, int b){
while(super_pai[a] != super_pai[b]){
if(nivel[a] > nivel[b]) a = super_pai[a];
else b = super_pai[b];
}
while(a != b){
if(nivel[a] > nivel[b]) a = pai[a];
else b = pai[b];
}
return a;
}
int main(){
while(scanf("%d", &n) && n){
segmento = 0;
for(int i = 0;i < n;i++) grafo[i].clear(), visited[i] = false, dist[i] = 0LL, super_pai[i] = -1, nivel[i] = 0;
for(int i = 1;i < n;i++){
int x;
lint d;
scanf("%d %lld", &x, &d);
grafo[x].push_back(i);
pai[i] = x;
dist[i] = dist[x] + d;
nivel[i] = nivel[x] + 1;
if(nivel[i] > segmento) segmento = nivel[i];
}
//printf("%d %d\n", nivel[0], nivel[1]);
//printf("%d\n", segmento);
segmento = (int)floor(sqrt(segmento));
monta_super_pai(0, 1);
int q;
scanf("%d", &q);
for(int i = 1;i <= q;i++){
int a, b;
scanf("%d %d", &a, &b);
if(i > 1) printf(" ");
printf("%lld", dist[a] + dist[b] - 2*dist[lca(a, b)]);
}
printf("\n");
}
return 0;
}

view raw

tuneis.cpp

hosted with ❤ by GitHub