結果
問題 | No.2634 Tree Distance 3 |
ユーザー | ゼット |
提出日時 | 2024-02-16 23:34:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,976 ms / 3,000 ms |
コード長 | 1,713 bytes |
コンパイル時間 | 570 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 223,824 KB |
最終ジャッジ日時 | 2024-02-16 23:35:49 |
合計ジャッジ時間 | 80,972 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge16 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,330 ms
204,208 KB |
testcase_01 | AC | 1,368 ms
215,184 KB |
testcase_02 | AC | 1,240 ms
214,932 KB |
testcase_03 | AC | 1,304 ms
214,600 KB |
testcase_04 | AC | 1,311 ms
203,956 KB |
testcase_05 | AC | 1,456 ms
155,520 KB |
testcase_06 | AC | 1,489 ms
155,520 KB |
testcase_07 | AC | 1,501 ms
156,024 KB |
testcase_08 | AC | 1,152 ms
217,524 KB |
testcase_09 | AC | 1,194 ms
217,772 KB |
testcase_10 | AC | 1,200 ms
217,324 KB |
testcase_11 | AC | 1,164 ms
217,728 KB |
testcase_12 | AC | 1,168 ms
218,420 KB |
testcase_13 | AC | 1,187 ms
158,592 KB |
testcase_14 | AC | 1,221 ms
158,448 KB |
testcase_15 | AC | 1,213 ms
158,452 KB |
testcase_16 | AC | 1,120 ms
190,076 KB |
testcase_17 | AC | 721 ms
138,456 KB |
testcase_18 | AC | 878 ms
155,000 KB |
testcase_19 | AC | 927 ms
173,220 KB |
testcase_20 | AC | 365 ms
108,072 KB |
testcase_21 | AC | 1,840 ms
157,180 KB |
testcase_22 | AC | 1,651 ms
157,412 KB |
testcase_23 | AC | 1,581 ms
157,560 KB |
testcase_24 | AC | 1,520 ms
218,452 KB |
testcase_25 | AC | 1,548 ms
218,376 KB |
testcase_26 | AC | 1,562 ms
218,056 KB |
testcase_27 | AC | 1,976 ms
157,944 KB |
testcase_28 | AC | 1,760 ms
157,060 KB |
testcase_29 | AC | 1,816 ms
157,688 KB |
testcase_30 | AC | 1,687 ms
156,808 KB |
testcase_31 | AC | 1,724 ms
157,312 KB |
testcase_32 | AC | 1,632 ms
156,676 KB |
testcase_33 | AC | 1,094 ms
128,348 KB |
testcase_34 | AC | 367 ms
88,948 KB |
testcase_35 | AC | 716 ms
108,820 KB |
testcase_36 | AC | 489 ms
96,700 KB |
testcase_37 | AC | 785 ms
113,940 KB |
testcase_38 | AC | 142 ms
78,096 KB |
testcase_39 | AC | 140 ms
78,224 KB |
testcase_40 | AC | 128 ms
77,788 KB |
testcase_41 | AC | 124 ms
77,892 KB |
testcase_42 | AC | 128 ms
77,872 KB |
testcase_43 | AC | 588 ms
120,740 KB |
testcase_44 | AC | 389 ms
105,980 KB |
testcase_45 | AC | 1,261 ms
187,576 KB |
testcase_46 | AC | 881 ms
152,244 KB |
testcase_47 | AC | 1,436 ms
217,984 KB |
testcase_48 | AC | 1,469 ms
196,584 KB |
testcase_49 | AC | 1,460 ms
199,708 KB |
testcase_50 | AC | 1,436 ms
195,928 KB |
testcase_51 | AC | 1,506 ms
196,104 KB |
testcase_52 | AC | 1,469 ms
196,216 KB |
testcase_53 | AC | 116 ms
77,712 KB |
testcase_54 | AC | 120 ms
77,656 KB |
testcase_55 | AC | 119 ms
77,748 KB |
testcase_56 | AC | 103 ms
77,080 KB |
testcase_57 | AC | 119 ms
77,720 KB |
testcase_58 | AC | 44 ms
55,608 KB |
testcase_59 | AC | 44 ms
55,608 KB |
testcase_60 | AC | 1,411 ms
214,472 KB |
testcase_61 | AC | 1,365 ms
203,708 KB |
testcase_62 | AC | 1,426 ms
201,728 KB |
testcase_63 | AC | 1,129 ms
223,824 KB |
testcase_64 | AC | 761 ms
172,672 KB |
testcase_65 | AC | 1,038 ms
212,972 KB |
testcase_66 | AC | 383 ms
120,600 KB |
testcase_67 | AC | 345 ms
113,444 KB |
testcase_68 | AC | 1,027 ms
158,724 KB |
testcase_69 | AC | 1,069 ms
158,980 KB |
testcase_70 | AC | 1,043 ms
158,716 KB |
ソースコード
N=int(input()) A=list(map(int,input().split())) G=[[] for i in range(N)] for i in range(N-1): a,b=map(int,input().split()) G[a-1].append(b-1) G[b-1].append(a-1) p=[[0]*N for i in range(20)] dist=[-1]*N from collections import deque S=deque() S.append(0) dist[0]=0 while S: x=S.pop() for y in G[x]: if dist[y]>=0: continue dist[y]=dist[x]+1 p[0][y]=x S.append(y) for k in range(1,20): for i in range(N): p[k][i]=p[k-1][p[k-1][i]] def LCA(a,b): x=a y=b if dist[x]>dist[y]: x,y=y,x u=dist[y]-dist[x] for k in range(20): if (u>>k)&1: y=p[k][y] if x==y: return x for k in range(19,-1,-1): if p[k][x]!=p[k][y]: x=p[k][x] y=p[k][y] y=p[0][y] return y T={} B=set() for i in range(N): B.add(A[i]) B=list(B) B.sort() M=len(B) for i in range(M): T[B[i]]=i R=[[] for i in range(M)] for i in range(N): R[T[A[i]]].append(i) result=[0]*N pos1=-1 pos2=-1 z=0 for i in range(M-1,-1,-1): for y in R[i]: if pos1==-1: pos1=y elif pos2==-1: pos2=y l=LCA(pos1,pos2) d=dist[pos1]+dist[pos2]-2*dist[l] z=d result[y]=d else: l1=LCA(pos1,y) l2=LCA(pos2,y) d1=dist[pos1]+dist[y]-2*dist[l1] d2=dist[pos2]+dist[y]-2*dist[l2] result[y]=max(d1,d2) if max(d1,d2)>z: z=max(d1,d2) if d1>=d2: pos2=y else: pos1=y if len(R[i])>1: for y in R[i]: l1=LCA(pos1,y) l2=LCA(pos2,y) d1=dist[pos1]+dist[y]-2*dist[l1] d2=dist[pos2]+dist[y]-2*dist[l2] result[y]=max(d1,d2) if max(d1,d2)>z: z=max(d1,d2) if d1>=d2: pos2=y else: pos1=y print(*result)