Solução Informática - Nível Avançado - Semana 12

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;

	}

view raw

BegginForANode.cpp

hosted with ❤ by GitHub

Note que existem outras soluções para esse problema que utilizam outros conceitos, como decomposição em centroides e Heavy-Light Decomposition.