1872. Снеговики

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

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

· либо добавляет ему сверху один шар;

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

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

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

t m – клонировать снеговика номер t (0 ≤ t < i) и добавить сверху шар массой m (0 < m ≤ 1000);

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

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

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

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

Пример входа	Пример выхода
8 0 1 1 5 2 4 3 2 4 3 5 0 6 6 1 0	74

РЕШЕНИЕ

структуры данных - стек

Анализ алгоритма

Информацию о снеговиках будем хранить в векторе структур Man. Структура Man содержит массу снеговика, а также номер его предка – номер снеговика, который был клонирован для его получения.

· Если i-ый снеговик получается из t-го (t < i) добавлением шара снега массой m, то в v[i] заносим снеговика с параметрами Man(v[t].Weight + m, t).

· Если i-ый снеговик получается из t-го (t < i) удалением верхнего шара, то получится снеговик, из которого был клонирован t-ый (номер снеговика, из которого был получен t-ый, содержится в v[t].Parent). То есть v[i] следует положить равным v[v[t].Parent].

Считаем, что нулевой снеговик получен сам из себя и имеет массу 0. То есть значению v[0] присвоим снеговика Man(0, 0).

Пример

Рассмотрим приведенный в примере процесс клонирования снеговиков. Сверху над каждым снеговиком приведена его масса.

Шестой снеговик получается из пятого удалением верхнего шара. Следовательно он должен совпадать с четвертым снеговиком (из которого получился пятый). Но поскольку четвертый снеговик получен из третьего добавлением шара, то можно рассматривать шестого снеговика как такового, который получен из третьего добавлением шара с массой 2.

Восьмой снеговик получается из первого удалением верхнего шара. Он станет равным нулевому снеговику. Но поскольку считается, что нулевой снеговик получается из нулевого, то восьмой снеговик считается образованным из нулевого.

Реализация алгоритма

Объявим вектор пар v, в котором будем хранить информацию о снеговиках.

struct Man

{

int Weight;

int Parent;

Man(int Weight, int Parent) : Weight(Weight), Parent(Parent) {};

};

vector<Man> v;

Моделируем процесс создания снеговиков как описано в анализе задачи.

scanf("%d",&n); sum = 0;

v.push_back(Man(0,0));

for(i = 1; i <= n; i++)

{

scanf("%d %d",&t,&m);

if (m > 0) v.push_back(Man(v[t].Weight + m, t));

else v.push_back(v[v[t].Parent]);

sum += v[i].Weight;

}

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

printf("%lld\n",sum);

Реализация при помощи статического массива

#include <stdio.h>

struct Pair

{

int Number;

int Weight;

} Sman[200001];

int i, n, t, m;

long long sum;

int main(void)

{

scanf("%d",&n); sum = 0;

for(i = 1; i <= n; i++)

{

scanf("%d %d",&t,&m);

if (m > 0)

{

Sman[i].Number = t;

Sman[i].Weight = Sman[t].Weight + m;

}

else Sman[i] = Sman[Sman[t].Number];

sum += Sman[i].Weight;

}

printf("%lld\n",sum);

return 0;

}

Java реализация

Реализуем класс Pair.

import java.util.*;

public class Main

{

public static class Pair

{

int First, Second;

public Pair(int First, int Second)

{

this.First = First;

this.Second = Second;

}

}

public static void main(String[] args)

{

Pair v[] = new Pair[200010];

v[0] = new Pair(0,0);

Scanner con = new Scanner(System.in);

int n = con.nextInt();

long sum = 0;

for(int i = 1; i <= n; i++)

{

int t = con.nextInt(), m = con.nextInt();

if (m > 0)

v[i] = new Pair(t,v[t].Second + m);

else v[i] = v[v[t].First];

sum += v[i].Second;

}

System.out.println(sum);

}

}