B :: Directory Tree
Time Limit: 2 Seconds Memory Limit: 66560 KB
In the ZIP archive, it maintains the relative path and name of all the compressed files and directories in it. When the GUI software(such as WinZIP) opens the archive, it can reconstruct the tree structure from these information. Now it's your task to write a program to do the job.
Input
The input have multiple cases.
In each test case, the first line is a number N (1<=N<=20000),
indicating the number of files and directories in the ZIP archive.
Then n lines follows, each line has the relative path and name of the
file or directory(each line has no more than 260 characters).
Notice:
1.The ASCII value of all the characters in the path and file name lies
in [0x20,0x7F]. And the following characters will not appear in the path
and file name:'/:*?"<>|'. '\' is only used as path delimiter.
2.The path and name is case-sensitive.
3.Directory is ended by '\'.
4.There will not be duplicated items in the input.
5.The size of whole input will not exceeds 2MB.
Output
Assume all the paths are relative to the 'root' directory. Start from
the root directory, for each directory, first output its name, then
output all the subdirectories recursively in alphabatic order, then
output all the files in it alphabatically.
Notice:To make the tree look nice, before printing the name, you should
first output n leading tabs('\t') according to its level relative to the
root directory(for example, you should output one tab if the file is in
the 'root' folder and output two tabs if it is in the subdirectories of
the 'root' folder).
To keep the size of output, you are not required to output the tree directly. Just output its 'hash' which is defined as:
unsigned int Hash(const char *Key) {
unsigned int HashVal=0,i=1;
while (*Key) {
HashVal+=(*Key++)*(i++);
HashVal%=0x8000000B;
HashVal*=0xFFFFFFEF;
}
return HashVal;
}Notice: cin and cout is not recommended here, use them at your own risk!
Hint for sample output:
The directory tree is as follows:
root
a
d
a
bc
ab
cd
d
c
b
and 966637654=hash("root\n\ta\n\t\td\n\t\t\ta\n\t\tbc\n\tab\n\t\tcd\n\t\td\n\tc\n\tb\n")
Sample Input
6 b c\ ab\cd a\bc ab\d a\d\a
Sample Output
966637654Submit