Solução por Pedro Racchetti
Conhecimentos prévios necessários:
Nesse problema, podemos representar a Nlogônia como uma árvore, onde temos que encontrar uma vértice $$x$$, utilizando as perguntas descritas no enunciado.
Primeiro, podemos enraizar a árvore na cidade $$1$$, achando a distância de todos as cidades até $$1$$ com uma DFS. Podemos então perguntar a distância de $$1$$ até o tesouro. Chame essa distância de $$d$$. Se $$d$$ for $$0$$, sabemos que a resposta é $$1$$, e podemos encerrar o problema. Caso contrário, podemos então encontrar todas as cidades com distância $$d$$ de $$1$$, e armazená-las em um vetor, ordenado pela ordem em que a DFS os alcança.
Como esse vetor está ordenado, podemos aplicar uma espécie de busca binária, da seguinte maneira:
Suponha que estamos testando no intervalo $$[l, r]$$. Testaremos a cidade $$k$$ de índice $$m$$ no vetor, onde $$m = (l+r)/2$$.
Podemos perguntar “$$?$$ $$1$$ $$k$$”, que irá nos resultar uma distância $$2L$$. Temos então dois casos:
- $$2L = 0$$ Nesse caso, $$k = x$$. Isso acontecerá ao menos uma vez na busca binária;
- $$2L \neq 0$$ Nesse caso, podemos encontrar com Sparse Table as cidades $$u$$ e $$v$$, tal que $$u$$ é a $$(L – 1)$$-ésima cidade no caminho entre $$k$$ e $$x$$ e $$v$$ é $$L$$-ésimo cidade no caminho entre $$k$$ e $$x$$, além de ser o LCA entre essas duas cidades, já que como $$x$$ e $$k$$ estão na mesma distancia de $$1$$, a distância entre $$x$$ e $$v$$ deve ser igual à distância entre $$k$$ e $$v$$
Finalmente, podemos perguntar “$$?$$ $$2$$ $$v$$” tendo como resposta $$p$$. Se $$p$$ vêm antes de $$u$$ na ordem da DFS, podemos mover o intervalo para $$[l, m-1]$$. Caso contrário, movemos o intervalo para $$[m+1, r]$$.
Portanto, o número máximo de perguntas é $$2*log_2(n)+1$$, que é menor que $$36$$.
Complexidade: $$O(n*log_2(n))$$
Segue o código, para melhor compreensão:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| const int MAX = 212345; | |
| int w[MAX], p[MAX], n, dp[MAX][30], prof[MAX], tin[MAX]; | |
| int marc[MAX]; | |
| std::vector<int> grafo[MAX]; | |
| //Calculamos a ordem da DFS, a sparse table e a | |
| //distancia de todas as cidades em relação à cidade 1 | |
| int T = 0; | |
| void dfs(int u, int p, int prof) { | |
| tin[u] = T++; | |
| ::prof[u] = prof; | |
| dp[u][0] = p; | |
| marc[u] = 1; | |
| for(int i = 1; i < 22; i++) | |
| dp[u][i] = dp[dp[u][i-1]][i-1]; | |
| for(int i = 0; i < grafo[u].size(); i ++){ | |
| int viz = grafo[u][i]; | |
| if(marc[viz]) continue; | |
| dfs(viz, u, prof + 1); | |
| } | |
| } | |
| pair<int, int> lcamodificado(int v, int alt2, int alt1) { | |
| //nessa funcão, encontramos os vértices u e v como descrito na solução | |
| int aux = v; | |
| pair<int, int> ans; | |
| for(int k = 18; k >= 0; k–) | |
| if(prof[dp[v][k]] >= alt1) | |
| v = dp[v][k]; | |
| ans.second = max(1,v); | |
| for(int k = 18; k >= 0; k–){ | |
| if(prof[dp[aux][k]] >= alt2 ) | |
| aux = dp[aux][k]; | |
| } | |
| ans.first = aux; | |
| return ans; | |
| } | |
| vector<int> vetorteste; | |
| bool cmp(int a, int b){ | |
| //estabelecemos o critério de comparacao do vetorteste | |
| return tin[a] < tin[b]; | |
| } | |
| int main(){ | |
| prof[0] = 0; | |
| cin >> n; | |
| for(int i = 1; i < n; i++){ | |
| int u,v; | |
| cin >> u >> v; | |
| grafo[u].push_back(v); | |
| grafo[v].push_back(u); | |
| } | |
| dfs(1, 1, 0); | |
| cout << "? 1 1" << endl; | |
| cout.flush(); | |
| int d; | |
| cin >> d; | |
| if(d == 0){ | |
| // | |
| cout << "! 1" << endl; | |
| cout.flush(); | |
| return 0; | |
| } | |
| for(int i = 1; i <= n; i++){ | |
| if(prof[i] == d) vetorteste.push_back(i); | |
| } | |
| sort(vetorteste.begin(), vetorteste.end(), cmp); | |
| int l = 0, r = vetorteste.size() – 1; | |
| int ans; | |
| while(l < r){ | |
| int m = (l + r)/2; | |
| cout << "? 1 " << vetorteste[m] << endl; | |
| cout.flush(); | |
| int L; | |
| cin >> L; | |
| if(L == 0){ | |
| //se L for 0, encontramos o tesouro! | |
| cout << "! " << vetorteste[m] << endl;; | |
| cout.flush(); | |
| return 0; | |
| } | |
| //encontramos as cidades V e U como descrito na solução | |
| pair<int, int> VeU = lcamodificado(vetorteste[m], prof[vetorteste[m]] – L/2, prof[vetorteste[m]] -((L/2) – 1)); | |
| cout <<"? 2 " << VeU.first << endl; | |
| cout.flush(); | |
| int p; | |
| cin >> p; | |
| if(tin[p] < tin[VeU.second]) r = m-1; | |
| else l = m + 1; | |
| } | |
| cout << "! " << vetorteste[l]<< endl;; | |
| cout.flush(); | |
| return 0; | |
| } | |
Note que existem outras soluções para esse problema que utilizam outros conceitos, como decomposição em centroides e Heavy-Light Decomposition.