發表新討論
#20951: 求大神優化(8~13一直TLEQQ)


youngyoung (06 蘇昱揚 306)

學校 : 臺北市私立延平高級中學
編號 : 98924
來源 : [180.217.13.133]
最後登入時間 ：
2022-05-03 14:31:59
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [180.217.128.223] | 發表日期 : 2020-03-22 10:21
nodes = eval(input())
leaf = []
TreeList = [[i + 1] for i in range(nodes)] #set node
for i in range(nodes): #set NumOfSons, Sons
  lst = input()
  NumOfSons = eval(lst.split()[0])
  Sons = [eval(j) for j in lst.split()[1:]]
  TreeList[i].append(NumOfSons)
  TreeList[i].append(tuple(Sons))
  if NumOfSons == 0:
    leaf.append(i)
for i in range(nodes): #set Father
  if TreeList[i][1] != 0:
    for j in range(TreeList[i][1]):
      TreeList[TreeList[i][2][j] - 1].append(i + 1)
for i in range(nodes): #find root
  if len(TreeList[i]) == 3:
    root = i + 1
    TreeList[i].append(0)
    break
for i in range(nodes):
  TreeList[i].append(0)
for i in leaf: #set possible hight
  hight = 0
  j = i
  while j != root - 1:
    if hight > TreeList[j][4]:
      TreeList[j][4] = hight
    hight += 1
    j = TreeList[j][3] - 1
  if hight > TreeList[root - 1][4]:
    TreeList[root - 1][4] = hight
TotalHight = 0
for i in range(nodes):
  TotalHight += TreeList[i][4]
print(root)
print(TotalHight)
 
#20964: Re:求大神優化(8~13一直TLEQQ)


asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [61.223.61.220] | 發表日期 : 2020-03-22 13:09

參考

https://chiendavid.blogspot.com/2020/03/zerojudge-c463-apcs-tree-analyses.html

 
#20978: Re:求大神優化(8~13一直TLEQQ)


youngyoung (06 蘇昱揚 306)

學校 : 臺北市私立延平高級中學
編號 : 98924
來源 : [180.217.13.133]
最後登入時間 ：
2022-05-03 14:31:59
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [101.12.139.165] | 發表日期 : 2020-03-23 20:16



謝謝您的幫忙和詳細的註解

 
ZeroJudge Forum