AtCoder Grand Contest 009

Submission #1077307

Source codeソースコード

from collections import defaultdict
import sys
sys.setrecursionlimit(110000)

def dfs(i):
	if i not in H: return 0
	if memo[i]>=0: return memo[i]
	a=sorted(-dfs(e) for e in H[i])
	memo[i]=max(i+1-a[i]for i in xrange(len(a)))
	return memo[i]
     
N=int(sys.stdin.readline())
memo=[-1]*N
H=defaultdict(list)
for i,e in enumerate(xrange(N-1)):H[int(sys.stdin.readline())-1].append(i+1)
dfs(N//2)
print(dfs(0))

Submission

Task問題 B - Tournament
User nameユーザ名 002_ciel
Created time投稿日時
Language言語 Python2 (2.7.6)
Status状態 AC
Score得点 800
Source lengthソースコード長 423 Byte
File nameファイル名
Exec time実行時間 1009 ms
Memory usageメモリ使用量 152760 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - s1.txt,s2.txt,s3.txt
All 800 / 800 01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt,20.txt,21.txt,22.txt,23.txt,24.txt,25.txt,26.txt,27.txt,28.txt,29.txt,30.txt,31.txt,32.txt,33.txt,34.txt,35.txt,36.txt,37.txt,38.txt,39.txt,40.txt,41.txt,42.txt,43.txt,44.txt,45.txt,46.txt,47.txt,48.txt,49.txt,50.txt,s1.txt,s2.txt,s3.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01.txt AC 324 ms 16432 KB
02.txt AC 299 ms 16432 KB
03.txt AC 289 ms 16432 KB
04.txt AC 291 ms 16432 KB
05.txt AC 311 ms 16432 KB
06.txt AC 291 ms 16432 KB
07.txt AC 311 ms 16432 KB
08.txt AC 292 ms 16432 KB
09.txt AC 296 ms 16432 KB
10.txt AC 309 ms 16432 KB
11.txt AC 1009 ms 152760 KB
12.txt AC 719 ms 103988 KB
13.txt AC 612 ms 82356 KB
14.txt AC 525 ms 61092 KB
15.txt AC 483 ms 74200 KB
16.txt AC 405 ms 49672 KB
17.txt AC 370 ms 34440 KB
18.txt AC 332 ms 23076 KB
19.txt AC 339 ms 19376 KB
20.txt AC 322 ms 18608 KB
21.txt AC 122 ms 7672 KB
22.txt AC 125 ms 7300 KB
23.txt AC 124 ms 7144 KB
24.txt AC 127 ms 7416 KB
25.txt AC 124 ms 7160 KB
26.txt AC 127 ms 7032 KB
27.txt AC 129 ms 7416 KB
28.txt AC 133 ms 7544 KB
29.txt AC 135 ms 7544 KB
30.txt AC 146 ms 7800 KB
31.txt AC 284 ms 16304 KB
32.txt AC 237 ms 13872 KB
33.txt AC 213 ms 12596 KB
34.txt AC 184 ms 9652 KB
35.txt AC 170 ms 9396 KB
36.txt AC 178 ms 8244 KB
37.txt AC 145 ms 7416 KB
38.txt AC 133 ms 6904 KB
39.txt AC 126 ms 7160 KB
40.txt AC 124 ms 7160 KB
41.txt AC 18 ms 2808 KB
42.txt AC 17 ms 2808 KB
43.txt AC 18 ms 2808 KB
44.txt AC 18 ms 2808 KB
45.txt AC 18 ms 2808 KB
46.txt AC 18 ms 2808 KB
47.txt AC 18 ms 2808 KB
48.txt AC 18 ms 2808 KB
49.txt AC 18 ms 2808 KB
50.txt AC 18 ms 2808 KB
s1.txt AC 18 ms 2808 KB
s2.txt AC 18 ms 2808 KB
s3.txt AC 18 ms 2808 KB