Keke's Secret

Posted on 21/01/2019, in Career.

infoCredit to Ziyi

Question Description

Keke has a very strange habit. He stores all his confidential information as folder names in a disk partition. Each folder has an id, and Keke’s confidential information is a combination of the folder names moving from the S folder to the T folder (including S and T). Since Keke’s disk is slow, the time to open a folder is equal to the number of subfolders. Given id, name, parent directory of each folder, as well as start folder id, end folder id, calculate the length of Keke’s confidential information, and total time required to find this confidential information.

Assume you are in the root folder, and the time spent is 0; every time you open a folder, you can know the current folder name and all subfolder names.

Input format

The first line contains 3 integers $n$, $s$, $t$. $n$ is the number of folders, $s$ is the start folder id, $t$ is the end folder id. For next $n$ lines, each line has 2 integers $i$, $p_i$ and one string $s_i$ (without spaces) of up to 255 in length: $i$ is the folder id, $p_i$ is the parent directory id ($p_i$ = 0 means the folder is the first-level folder in the root directory), $s_i$ is the name of the folder.

We also have the following constraints for the input: $3\leq n \leq 10000, \, 1\leq i \leq n, \, 0\leq p_i \leq n$.

Output format

The output file has 2 number. The first line is the length of Keke’s confidential information, and the second line is the total time.


Sample input

6 1 5
1 2 Ke 
2 3 Ke 
3 0 .
4 3 he 
5 4 h
6 5 .ehe

Sample output

8 4

Function signature

vector<int> lengthAndTime(int n, int start, int end, const & vector<pair<int, string>> folder);