TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

99.4% (165/166)

Submission's AC Ratio

75.2% (245/326)

Tags

Description

如果想要忠於原味可以從這裡找到題目:
http://www.cs.nthu.edu.tw/info_race93/93problem-f.pdf

很久很久以前,銀河系有一個科技極度發達的帝國存在,這個帝國有著許許多多的星球所組成,這些星球之間有主從關係,除了帝國首都之外,其他的星球均從屬於自己專屬的主星。

由於銀河是相當的浩瀚,主要的旅行方式是空間跳躍,不管這兩個星球有多遠只要花一小時就抵達目的地。為了維護帝國間的和平與安定,帝國當局是嚴格的管制空間跳躍的使用,只允許主星到從屬星以及從屬星到主星之間的的空間跳躍。假定銀河帝國中,只有一個帝國首都,首都本身也是一個星球,每個星球只有一個專屬的主星,但一個星球可以有許多從屬星。並且不會發生循環從屬的關係,即不會發生如下情況:S1是S2的主星,S2是S3的主星...Sn-1是Sn的主星,Sn是S1的主星。

以下圖為例,1號星與2號星為0號星(也就是帝國首都)的從屬星,3號星是1號星的從屬星,4號星是2號星的從屬星。在這個例子中,從3號星到2號星作星際旅行需要3小時:3號星 → 1號星,1號星 → 0號星,0號星 → 2號星。而在這個星系中作星際旅行,最多需要花4小時,也就是從3號星旅行到4號星。

現在你的任務是估計銀河帝國之中,任意選兩個星球作為起點與終點進行空間跳躍旅行,最多需要花多少時間?(以上圖為例,答案是4個小時。)

Input Format

第一行將有一個數字n (n<=10000),代表了銀河帝國中有 n個星球。緊接下來會有 n行,接下來的每行依序都代表了一個星球的從屬星名單。為了簡化輸入的複雜度,將由0到 n-1 的數字來替代星球名稱,0就是帝國首都,而且只有數字小的才可以當數字大的主星。每行的格式:"從屬星1 從屬星2 … -1",最後的-1代表從屬星名單結束,如果是單一一行的-1,代表該星球沒有從屬星。

Output Format

輸出一行,包含一個數字。即任選兩個星球,最多需要花多少小時才能藉由空間跳躍從起點到達目的地。

Sample Input 1

5
1 2 -1
3 -1
4 -1
-1
-1

Sample Output 1

4

Sample Input 2

6
1 -1
2 3 4 5 -1
-1
-1
-1
-1

Sample Output 2

2

Hints

Problem Source

原TIOJ1152 / 93全國賽(prob 1)。

Subtasks

No. Testdata Range Score
1 0 33
2 1 33
3 2 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1
1 900 65536 262144 2
2 900 65536 262144 3