546 . Contraction Maps
Description
Byteland is an amazing country, its roads are constructed just like a binary tree, and all the people live in the tree leaves. They usually work at internal nodes, and go back to their home at night. On weekends, some people will gather together and have a nice tea time. But it is the problem to gather all the people together -- the map was too large to find everyone who should be invited to have a cup of tea.
Please write a program that, reads a map of Byteland from standard input, and reduces the map into smaller ones.
Every one who should participate in the same group would have same group names. All you have to do is to reduce the map for all groups, pick up all the people in the same group and get rid of the useless internal nodes.
For example, if we have three groups called "a", "ab", and "c", we can construct three maps for "a", "ab", and "c" respectively. After redraw the map, we take out the unnecessary internal nodes and form the maps below.
Input Format
There are multiple test cases in the input file. For each test case:
The first line contains an integer n (1<=n<=2,000,000) denoting the number of nodes in Byteland.
From the second line to the (n+1)th line, there would be a pre-order traversal in Byteland. In each line there is a string contains either a single star '*' denoting an internal node or a group name. Each node is labeled with a number which exactly preserves the order of the traversal.
All names are composed of non-capital letters, and in a test case the total length of names will not greater than 1,000,000.
Output Format
Output the pre-order traversal of the reduced maps, one line per map, sorted by the group name. There is no need to print any blank lines between test cases.
Sample Input 1
11 * * a ab * * c ab * c c 3 * b a
Sample Output 1
3 1 4 8 5 7 9 10 11 3 2
Hints
Problem Source
Migrated from old NTUJ.
POI Camp 2008 Day1
Subtasks
| No. | Testdata Range | Score |
|---|