images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/12/2024 23:41:00

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1640. Family tree

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

Scientists on Antarctica have found a new species! They extracted one sample and took it to the laboratory for testing.
They quickly noticed the species reproduces quite often and that only one parent is required for reproduction. However after the parent reproduces twice, it becomes sterile and cannot reproduce again.
In spite of this the number of specimens in the laboratory skyrocketed and the need for family trees appeared.
They decided to draw the tree in a simple text editor using following conventions:
The names of the specimens will be written inside nice boxes using characters '-', '|' and 'o'. The center point of the upper and lower border will be marked by the character '+'. If the length of the border is even, '+' will be on the left of the two center points. 
o--+--o    o----+----o     o-+--o
|anton|    |anamarija|     |pero|
o--+--o    o----+----o     o-+--o

The boxes will be connected with links. One link connects two or more boxes on their respective '+' characters, with the parent specimen placed above it's children. The boxes and links must not overlap.
  +         +               +            
  |         |               |            
  o     o---o---o     o-----o-----o
  |     |       |     |           |
  +     +       +     +           +
If the parent has one child, a point to point (leftmost example) link is used. If the parent has two children, a branching link is used, with the older child on the left, and the younger on the right.
Branching links may be expanded in the horizontal direction as long as the number of '-' characters on both sides stays equal. Links cannot be expanded vertically.
Don't worry, you will not be asked to draw the tree, only determine the number of characters required to draw it. Space characters are not counted, only '-', '|', '+' , 'o' and letters in the names.
Input
The first line of input contains one integer `N` (`1\ ≤\ N\ ≤\ 300\ 000`), number of specimens in the laboratory.
The specimens are marked with numbers 1 to `N` in the order of birth, with the oldest marked 1 and youngest marked `N`.
The next `N` lines contain birth notes of all specimens in the order of birth. Each specimen (except the first whose parent is unknown) is described with two pieces of information:
  • name – sequence of at most 20 lowercase english alphabet characters
  • parent – one integer denoting the parent of this specimen
Output
The first and only line of input should contain the minimal number of characters needed to draw the family tree.

Sample Input 1

3 
adam 
kain 1 
abel 1

Sample Output 1

64

   o-+--o 
   |adam| 
   o-+--o 
     | 
  o--o--o 
  |     | 
o-+--oo-+--o 
|kain||abel| 
o-+--oo-+--o

Sample Input 2

12 
anton 
ana 1 
luka 1 
mia 2 
tea 3 
jakov 3 
semiramida 5 
dominik 5 
anamarija 4 
eustahije 4 
lovro 2 
lovro 11

Sample Output 2

371

                             o--+--o 
                             |anton| 
                             o--+--o 
                                | 
                   o------------o------------o 
                   |                         | 
                 o-+-o                     o-+--o 
                 |ana|                     |luka| 
                 o-+-o                     o-+--o 
                   |                         | 
           o-------o-------o              o--o--o 
           |               |              |     | 
         o-+-o          o--+--o         o-+-oo--+--o 
         |mia|          |lovro|         |tea||jakov| 
         o-+-o          o--+--o         o-+-oo--+--o 
           |               |              | 
     o-----o-----o         o        o-----o-----o 
     |           |         |        |           | 
o----+----o o----+----o o--+--oo----+-----o o---+---o 
|anamarija| |eustahije| |lovro||semiramida| |dominik| 
o----+----o o----+----o o--+--oo----+-----o o---+---o
Source: COCI 2009/2010, final contest
loading