Рет қаралды 99
Solução do problema Burocracia da terceira fase da OBI 2024, que caiu na P2 e PSenior.
Marque sua aula experimental: podio.digital/
Instagram: / opodio.digital
Aula de Binary Lifting: noic.com.br/ma...
Aula de Union-Find: noic.com.br/ma...
Enunciado:
O reino de Nlogônia funciona de uma maneira bem interessante. A fim de garantir que todos os nobres estão sendo monitorados,
cada um deles possui exatamente um superior direto, de tal forma que o nobre i é subordinado direto do nobre
p[i]. A única exceção a essa regra é o rei de Nlogônia, que será representado pelo índice 1 e não possui
nenhum superior. Note que um nobre pode supervisionar vários outros nobres.
De tempos em tempos, nobres precisam enviar relatórios para algum superior que está a k níveis acima na hierarquia.
Por exemplo se o nobre i precisa enviar um relatório para alguém 3 níveis acima, ele será entregue para o nobre
p[p[p[i]]]. Isso tornou o funcionamento do reino extremamente burocrático, pois dependendo do número de níveis,
a comunicação interna do reino se torna prejudicada.
Para remediar esse problema, o rei de Nlogônia fará decretos da seguinte forma:
ele escolherá algum nobre v e todos os nobres que estão subordinados a v (direta ou indiretamente)
passarão a ser subordinados diretos de v. Em outras palavras para todo u tal
que p[p[ ... u ...] = v, p[u] passa a ser v. Dizemos que essa é uma operação de reestruturação partindo de v.
Como Treinar para a OBI
Solução OBI 2024 Terceira Fase
Olimpíada Brasileira de Informática
Programação Competitiva
Arthur Lobo
IOI
Olimpíada Internacional de Informática
Vagas Olímpicas
#programação
#informatica
#matemática