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:
| #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.
