Подразделы

Другие разделы

Дата и время

05/04/2025 21:50:51

Авторизация

Задачи командного чемпионата

A. Калейдоскоп B. Forth C. Сокращение штатов D. Космическая станция E. Взлом кода F. Стратегия для игры G. Скульптура H. Основание системы счисления I. Primary Arithmetic J. JR;;P. EPT;F

C. Сокращение штатов

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (1)

В связи с кризисом Билл Виндоуз решил закрыть или продать не приносящие доходы подразделения и уволить некоторую часть сотрудников таким образом, чтобы его прибыль стала максимальна. При этом структура сложившихся иерархических отношений в компании должна сохраниться. Можно уволить в том числе главных менеджеров компании и оставить от компании наиболее доходную часть, продав менее доходные подразделения.

Напишите программу, которая определит персонал обновленной компании.

В первой строке ввода содержатся одно целое число

$N$ (

$1\ ≤\ N\ ≤\ 100 000$ ) – количество сотрудников в компании. Далее следует

$N$ строк, содержащих по два целых числа – доход от работы сотрудника

$p_i$ (

$-10 000\ ≤\ p_i\ ≤\ 10 000$ ) и номер сотрудника

$c_i$ (

$0\ ≤\ c_i\ ≤\ N$ ), который является его начальником (для топ-менеджера компании

$c_i=0$ ). В первой строке вывести одно целое число

$M$ (

$M\ ≥\ 0$ ) – количество оставшихся в компании сотрудников после сокращения, при котором доход компании становится максимальным. Во второй строке вывести

$M$ чисел через пробел — номера сотрудников в порядке возрастания. Если существует несколько вариантов решения, нужно вывести один (любой) из них.

Пример ввода

Пример вывода

3
1 2 3