e-olymp 1872. Снеговики

Задача: 

Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование — это процесс создания идентичной копии (клона).

В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин «Интернет-магазин аппаратов клонирования» аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:

  • либо добавляет ему сверху один шар;
  • либо удаляет из него верхний шар (если снеговик не пустой).

Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.

Входные данные

Первая строка содержит количество действий n (1n200000). В строке номер i+1 содержится описание действия:

  • t m — клонировать снеговика номер t (0t < i) и добавить сверху шар массой m (0 < m1000);
  • t 0 — клонировать снеговика номер t (0t < i) и удалить верхний шар. Гарантируется, что снеговик не пустой.

В результате действия i, описанного в строке i+1 создается снеговик номер i. Изначально имеется пустой снеговик с номером ноль.

Все числа во входном файле целые.

Выходные данные

Выведите суммарную массу построенных снеговиков.

Решение: Считываем n — количество действий. Задаем двухмерный массив размером [n+1][2]. Указываем значение первого элемента равное 0 и нулевого элемента равного -1, чтобы он ни на что не ссылался в начале.  В цикле считываем номер снеговика, которого нужно клонировать и массу шара, которую нужно добавить. Если масса шара равна 0, то мы клонируем снеговика и убираем последний его шар, ссылаясь на снеговика в котором этого шара еще не было. Если же масса шара не равно 0, то мы клонируем снеговика и добавляем ему шар массой m. Во второй ячейке указываем предка с которого строится новый снеговик. Выводим общую массу снеговиков.

Задача на e-olymp.

 

Код:

 

Тесты:

Input Output
8
0 1
1 5
2 4
3 2
4 3
5 0
6 6
1 0
74
4
0 3
1 2
2 1
1 1
18
Карагяур Мілан Сергійович
Карагяур Мілан Сергійович

Latest posts by Карагяур Мілан Сергійович (see all)

One thought on “e-olymp 1872. Снеговики

Добавить комментарий