結果
問題 | No.1098 LCAs |
ユーザー | 👑 Kazun |
提出日時 | 2020-06-26 23:26:25 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,012 bytes |
コンパイル時間 | 544 ms |
コンパイル使用メモリ | 87,008 KB |
実行使用メモリ | 234,356 KB |
最終ジャッジ日時 | 2023-09-18 08:11:00 |
合計ジャッジ時間 | 19,729 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 115 ms
72,504 KB |
testcase_01 | AC | 112 ms
72,256 KB |
testcase_02 | AC | 113 ms
72,356 KB |
testcase_03 | AC | 115 ms
72,344 KB |
testcase_04 | AC | 110 ms
72,404 KB |
testcase_05 | AC | 110 ms
72,244 KB |
testcase_06 | AC | 110 ms
72,496 KB |
testcase_07 | AC | 111 ms
72,488 KB |
testcase_08 | AC | 111 ms
72,612 KB |
testcase_09 | AC | 112 ms
72,460 KB |
testcase_10 | AC | 112 ms
72,244 KB |
testcase_11 | AC | 112 ms
72,560 KB |
testcase_12 | AC | 113 ms
72,396 KB |
testcase_13 | AC | 158 ms
78,620 KB |
testcase_14 | AC | 157 ms
78,496 KB |
testcase_15 | AC | 159 ms
78,748 KB |
testcase_16 | AC | 162 ms
79,164 KB |
testcase_17 | AC | 162 ms
78,788 KB |
testcase_18 | AC | 1,763 ms
234,356 KB |
testcase_19 | AC | 1,850 ms
228,512 KB |
testcase_20 | AC | 1,572 ms
225,876 KB |
testcase_21 | AC | 1,621 ms
227,532 KB |
testcase_22 | AC | 1,662 ms
230,408 KB |
testcase_23 | AC | 782 ms
172,988 KB |
testcase_24 | AC | 773 ms
172,892 KB |
testcase_25 | AC | 616 ms
163,944 KB |
testcase_26 | AC | 746 ms
220,496 KB |
testcase_27 | AC | 742 ms
211,852 KB |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
ソースコード
from functools import lru_cache from collections import deque N=int(input()) E={i:[] for i in range(1,N+1)} for _ in range(N-1): u,v=map(int,input().split()) E[u].append(v) E[v].append(u) T=[None]*(N+1) U=[False]*(N+1) F=[[] for _ in range(N+1)] Q=deque() T[1]=0 Q.append(1) while Q: v=Q.popleft() G=True for u in E[v]: if T[u]==None: Q.append(u) F[v].append(u) T[u]=1 G=False if G: U[v]=True @lru_cache(maxsize=2*10**6) def f(N): if U[N]: return 1 else: T=1 for v in F[N]: T+=f(v) return T def h(L): S=0 for p in L: S+=p*p T=sum(L) return T*T-S @lru_cache(maxsize=2*10**6) def g(N): if U[N]: return 1 else: C=[] for v in F[N]: C.append(f(v)) return h(C)+2*sum(C)+1 Z=[0]*(N+1) for i in range(2,N+1): Z[i]=g(i) Z[1]=N*N-sum(Z[2:]) for i in range(1,N+1): print(Z[i])