НачалоПодразделы
Другие разделы
| 1634. Croatian alphabet |
| 1635. Candy shop |
| 1636. Frequency sorter |
| 1637. Fractals |
| 1638. Walkway |
| 1639. Prime Number Circle |
| 1641. Наблюдения за звездами |
Дата и время
22/11/2024 17:37:28
1640. Family tree
Family tree
Олимпиадные задачи на английском языке| 04/07/2011 | Лето 2011 - дорешивание (11G) |
| 18/07/2011 | Лето 2011 - 11 (G) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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