Solução São João

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

O mapa das salas pode ser observado como um grafo. Mais que isso, sabemos, pelo número de arestas, que o grafo é uma árvore. Observe o exemplo de árvore abaixo:

tree

Suponha que o jogador começa da sala 1. A sala mais distante do começo é a sala 5, e para chegar nela, precisamos atravessar 3 corredores. Deste modo, se o número de corredores pelos quais podemos passar for no máximo 3, podemos passar por quatro salas (1, 3, 4, 5), descobrindo uma nova a cada corredor que visitamos. Porém, se o valor de for 4, por exemplo, não conseguirei visitar nenhuma nova sala. Se for 5, posso visitar, por exemplo, a sala 2, voltar para a sala 1 e depois fazermos o passeio que tínhamos feito anteriormente. O que ocorre é que, dado um caminho principal (caminho por onde não passo pela mesma aresta duas vezes) podemos descobrir de seus vértices explorando exatamente corredores. Se, entretanto, decidimos sair do caminho principal, descobriremos n salas passando por corredores e depois teremos que passar pelos mesmos corredores para voltarmos ao caminho principal, por onde saímos.

Deste modo, se temos salas no caminho principal e salas em caminhos secundários, passaremos por exatamente a+2b corredores para visitá-las. Deste modo, é sempre vantajoso ter o maior número possível de salas no caminho principal, para reduzirmos a quantidade de corredores. Para isso, o caminho principal deve ser exatamente o caminho entre o vértice de origem e o vértice mais distante dele.

Uma vez que sabemos que o comprimento deste caminho é o inteiro maior e podemos passar por corredores, podemos descobri exatamente 1 (sala inicial) + maior (salas no caminho principal) + (m-maior)/2 (salas em caminhos secundários). Observe que precisamos de cuidados para que o resultado não seja negativo, visto que nem sempre é maior que maior.

O problema agora resume-se a, para cada vértice, sabermos o valor de maior. Como o gafo é uma árvore, sabemos que o vértice mais distante será uma das pontas do diâmetro. Sejam d1 d2 duas pontas de um diâmetro. Para encontrá-los, usaremos o mesmo algoritmo mostrado no Problema Avançado da Semana 9. Faremos uma DFS no vértice 1 e o vértice mais distante será d1. Depois faremos uma DFS em d1 e o vértice mais distante será d2, lembrando de guardar todas as distâncias de um vértice v a d1 em dist[1][v].Por último, faremos uma DFS em d2 e guardaremos todas as distâncias de um vértice v a d2 em dist[2][v]. Chamaremos essas DFS's de dfs1, dfs2 e dfs3, respectivamente. Para cada query (A, M), o valor de maior será a distância para o mais distante entre d1 d2 (maior = max(sit[1][A], dist[2][Ad), e para encontrarmos a maior quantidade de salas exploráveis, usando a conta feita anteriormente mas com o cuidado para não a negativarmos ou imprimirmos uma quantidade de salas maior que n, basta imprimirmos o resultado da expressão: min(n, min(m+1, maior+1) + max(0, (m-maior)/2)). Segue o código para melhor entendimento.

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: