結果
問題 | No.1103 Directed Length Sum |
ユーザー | titia |
提出日時 | 2020-07-03 21:51:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,765 ms / 3,000 ms |
コード長 | 644 bytes |
コンパイル時間 | 195 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 275,928 KB |
最終ジャッジ日時 | 2024-09-17 00:19:20 |
合計ジャッジ時間 | 15,486 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
51,840 KB |
testcase_01 | AC | 38 ms
51,968 KB |
testcase_02 | AC | 632 ms
266,668 KB |
testcase_03 | AC | 557 ms
275,928 KB |
testcase_04 | AC | 932 ms
169,888 KB |
testcase_05 | AC | 1,765 ms
247,088 KB |
testcase_06 | AC | 590 ms
146,816 KB |
testcase_07 | AC | 156 ms
92,020 KB |
testcase_08 | AC | 212 ms
101,404 KB |
testcase_09 | AC | 110 ms
84,992 KB |
testcase_10 | AC | 295 ms
110,380 KB |
testcase_11 | AC | 1,003 ms
186,904 KB |
testcase_12 | AC | 550 ms
147,456 KB |
testcase_13 | AC | 275 ms
112,256 KB |
testcase_14 | AC | 101 ms
82,816 KB |
testcase_15 | AC | 462 ms
124,672 KB |
testcase_16 | AC | 1,252 ms
191,872 KB |
testcase_17 | AC | 1,332 ms
217,856 KB |
testcase_18 | AC | 279 ms
110,464 KB |
testcase_19 | AC | 1,049 ms
201,088 KB |
testcase_20 | AC | 131 ms
88,448 KB |
testcase_21 | AC | 199 ms
99,444 KB |
testcase_22 | AC | 842 ms
157,056 KB |
testcase_23 | AC | 497 ms
136,576 KB |
ソースコード
import sys input = sys.stdin.readline N=int(input()) E=[[] for i in range(N+1)] mod=10**9+7 D=[0]*(N+1) D[0]=-1 P=[-1]*(N+1) for i in range(N-1): x,y=map(int,input().split()) E[x].append(y) P[y]=x D[y]+=1 Parents=[1]*(N+1) Children=[1]*(N+1) R=D.index(0) Q=[R] TOP_SORT=[] while Q: x=Q.pop() TOP_SORT.append(x) for to in E[x]: Parents[to]=Parents[x]+1 Q.append(to) for t in TOP_SORT[::-1][:-1]: Children[P[t]]+=Children[t] ANS=0 for i in range(1,N+1): for to in E[i]: ANS=(ANS+Parents[i]*Children[to])%mod #print(i,to,Parents[i],Children[to]) print(ANS)