A. Party time limit per test 3 seconds memory limit per test 256 megabytes A company has…
- User
A. Party
time limit per test
3 seconds
memory limit per test
256 megabytes
A company has n employees numbered from 1 to n. Each employee either has no immediate manager or exactly one immediate manager, who is another employee with a different number. An employee A is said to be the superior of another employee B if at least one of the following is true:
Employee A is the immediate manager of employee B
Employee B has an immediate manager employee C such that employee A is the superior of employee C.
The company will not have a managerial cycle. That is, there will not exist an employee who is the superior of his/her own immediate manager.
Today the company is going to arrange a party. This involves dividing all n employees into several groups: every employee must belong to exactly one group. Furthermore, within any single group, there must not be two employees A and B such that A is the superior of B.
What is the minimum number of groups that must be formed?
Input
The first line contains integer n (1 ≤ n ≤ 2000) — the number of employees.
The next n lines contain the integers pi (1 ≤ pi ≤ n or pi = -1). Every pi denotes the immediate manager for the i-th employee. If pi is -1, that means that the i-th employee does not have an immediate manager.
It is guaranteed, that no employee will be the immediate manager of him/herself (pi ≠ i). Also, there will be no managerial cycles.
Output
Print a single integer denoting the minimum number of groups that will be formed in the party.
Examples
Input
Copy
5 -1 1 2 1 -1
Output
Copy
3
Note
For the first example, three groups are sufficient, for example:
Employee 1
Employees 2 and 4
Employees 3 and 5
Resolva esse problema usando python. Escreva as variáveis em português. Apenas comente o essencial
- Assistant
Aqui está a solução para o problema em Python. A ideia principal é construir um grafo de hierarquia e encontrar a profundidade máxima da árvore de gerenciamento, pois essa profundidade determina o número mínimo de grupos necessários (cada nível da hierarquia precisa de um grupo separado para evitar que superiores e subordinados estejam no mesmo grupo).
def calcular_profundidade(grafo, empregado, profundidades, visitados): # Se já calculamos a profundidade desse empregado, retornamos o valor memoizado if profundidades[empregado] != -1: return profundidades[empregado] # Se o empregado não tem subordinados, sua profundidade é 1 if not grafo[empregado]: profundidades[empregado] = 1 return 1 # Calculamos a profundidade máxima dos subordinados profundidade_maxima = 0 for subordinado in grafo[empregado]: if not visitados[subordinado]: visitados[subordinado] = True profundidade_maxima = max(profundidade_maxima, calcular_profundidade(grafo, subordinado, profundidades, visitados)) # A profundidade do empregado é 1 + a profundidade máxima dos subordinados profundidades[empregado] = 1 + profundidade_maxima return profundidades[empregado] # Leitura da entrada n = int(input()) gerentes = [] for _ in range(n): gerentes.append(int(input())) # Construção do grafo de hierarquia (lista de adjacência) grafo = [[] for _ in range(n)] raizes = [] # Empregados sem gerente (raízes da hierarquia) for i in range(n): if gerentes[i] == -1: raizes.append(i) else: # Adiciona o empregado i como subordinado do gerente gerentes[i]-1 grafo[gerentes[i] - 1].append(i) # Inicialização das variáveis para cálculo de profundidade profundidades = [-1] * n visitados = [False] * n # Calcula a profundidade máxima começando de cada raiz profundidade_maxima_global = 0 for raiz in raizes: if not visitados[raiz]: visitados[raiz] = True profundidade_maxima_global = max(profundidade_maxima_global, calcular_profundidade(grafo, raiz, profundidades, visitados)) # A profundidade máxima global é o número mínimo de grupos print(profundidade_maxima_global)Explicação Breve:
- Grafo de Hierarquia: Representamos a hierarquia como um grafo direcionado, onde cada empregado aponta para seus subordinados diretos.
- Profundidade: A profundidade de um empregado é 1 + a profundidade máxima de seus subordinados. Empregados sem subordinados têm profundidade 1.
- Mínimo de Grupos: A profundidade máxima da hierarquia determina o número mínimo de grupos, pois cada nível da hierarquia precisa de um grupo separado para evitar que superiores e subordinados estejam juntos.
- Memoização: Usamos
profundidadespara evitar recalcular a profundidade de empregados já visitados.
Complexidade:
- Tempo: O(n), onde n é o número de empregados, pois cada empregado é visitado no máximo uma vez.
- Espaço: O(n) para armazenar o grafo e as profundidades.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.