28a Olimpíada Brasileira de Informática
Startup
Devido ao seu sucesso na primeira fase da OBI, a startup IOI (Insatisfação Observada International) te ofereceu uma entrevista de estágio. Como parte do processo seletivo, você deve ajudar a empresa a avaliar a satisfação dos funcionários com seus empregos. Na hierarquia da startup, cada funcionário (exceto o fundador) possui um chefe. A empresa valoriza experiência no trabalho: o chefe de todo funcionário entrou na empresa antes dele. Para cada funcionário, os seus subordinados diretos são os funcionários que têm ele como chefe. Cada funcionário possui um salário mensal, e um estudo feito pela empresa revelou que existe um jeito simples de descobrir quais funcionários estão insatisfeitos: um funcionário está insatisfeito se, e somente se, algum dos seus subordinados diretos ganha mais do que ele (note que ele está satisfeito se seus subordinados ganham tanto quanto ele). Com o fim do trimestre chegando, o time de Recursos Humanos está considerando ajustar os salários de alguns funcionários, possivelmente aumentando ou reduzindo o valor mensal (porém, para evitar confusão, eles podem alterar o salário de cada funcionário no máximo uma vez). Mas, primeiro, eles precisam avaliar a insatisfação geral dos funcionários durante essa série de ajustes. Sua tarefa é, dada a estrutura hierárquica da empresa, os salários iniciais, e a sequência considerada de ajustes, determinar o número total de funcionários insatisfeitos inicialmente e após cada ajuste.Entrada
A primeira linha de entrada contém um inteiro N, indicando o número de funcionários da empresa. Os funcionários são identificados de 1 a N de acordo com a ordem em que entraram na startup. O fundador é identificado pelo número 1. Cada uma das N linhas seguintes descreve um funcionário: a linha i+1 contém dois inteiros, Ci e Si, indicando o chefe e o salário do funcionário i, respectivamente. É garantido que C1=1 (consideramos que o fundador é chefe de si mesmo) e que Cinão desfazemos o ajuste i-1 antes de fazer o ajuste i).Saída
Seu programa deve produzir A+1 linhas, cada uma contendo um único inteiro. A primeira linha deve conter o número de funcionários insatisfeitos antes dos ajustes. As próximas A linhas devem conter os números de funcionários insatisfeitos após cada ajuste.Restrições
- 1 ≤ N ≤ 100 000
- 0 ≤ A ≤ N
- C1=1 e 1 ≤ Ci1
- 1 ≤ Si ≤ 1 000 000
- 1 ≤ I ≤ N
- 1 ≤ X ≤ 1 000 000
- Os valores de I são todos distintos entre si (ou seja, cada funcionário tem o salário ajustado no máximo uma vez).
Informações sobre a pontuação
A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:- Subtarefa 1 (25 pontos): N ≤ 100 e A=0 -- ou seja, nenhum ajuste será feito, e você só precisa calcular a insatisfação total inicial. (Veja o exemplo de entrada 1.)
- Subtarefa 2 (25 pontos): N ≤ 2 000.
- Subtarefa 3 (25 pontos): Cada funcionário tem no máximo 2 subordinados diretos.
- Subtarefa 4 (25 pontos): Nenhuma restrição adicional.
Exemplos
Entrada
7 1 300 1 350 1 200 3 150 3 250 2 350 3 100 0 |
Saída
2 |
Entrada
5 1 500 1 400 2 300 3 450 4 300 2 4 300 3 500 |
Saída
1 0 1 |
Entrada
6 1 100 1 200 1 300 2 400 3 500 3 600 3 1 500 3 550 4 200 |
Saída
3 2 3 2 |