Skip to content
The Chat Archive
grok-3-preview-02-24· xAI LMArena Human Preference 140K

A. Party time limit per test 3 seconds memory limit per test 256 megabytes A company has…

  1. 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

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

    1. Grafo de Hierarquia: Representamos a hierarquia como um grafo direcionado, onde cada empregado aponta para seus subordinados diretos.
    2. Profundidade: A profundidade de um empregado é 1 + a profundidade máxima de seus subordinados. Empregados sem subordinados têm profundidade 1.
    3. 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.
    4. Memoização: Usamos profundidades para 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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.