結果
問題 | No.1333 Squared Sum |
ユーザー | tpyneriver |
提出日時 | 2020-10-31 07:41:54 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,214 bytes |
コンパイル時間 | 297 ms |
コンパイル使用メモリ | 87,164 KB |
実行使用メモリ | 164,540 KB |
最終ジャッジ日時 | 2023-09-29 10:07:22 |
合計ジャッジ時間 | 35,051 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,492 KB |
testcase_01 | AC | 75 ms
71,216 KB |
testcase_02 | AC | 75 ms
71,272 KB |
testcase_03 | TLE | - |
testcase_04 | TLE | - |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | AC | 1,675 ms
161,656 KB |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | AC | 74 ms
71,308 KB |
testcase_17 | AC | 74 ms
71,396 KB |
testcase_18 | AC | 75 ms
71,396 KB |
testcase_19 | AC | 74 ms
71,580 KB |
testcase_20 | AC | 76 ms
71,312 KB |
testcase_21 | AC | 76 ms
71,388 KB |
testcase_22 | AC | 75 ms
71,576 KB |
testcase_23 | AC | 76 ms
71,584 KB |
testcase_24 | AC | 76 ms
71,348 KB |
testcase_25 | AC | 75 ms
71,524 KB |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | AC | 1,809 ms
158,260 KB |
testcase_30 | AC | 881 ms
111,880 KB |
testcase_31 | AC | 550 ms
96,592 KB |
testcase_32 | AC | 1,409 ms
126,012 KB |
testcase_33 | AC | 1,114 ms
116,480 KB |
testcase_34 | AC | 1,928 ms
139,660 KB |
testcase_35 | AC | 1,470 ms
124,980 KB |
testcase_36 | AC | 762 ms
107,416 KB |
testcase_37 | AC | 822 ms
108,740 KB |
testcase_38 | AC | 904 ms
112,040 KB |
testcase_39 | AC | 1,513 ms
132,532 KB |
testcase_40 | AC | 634 ms
164,540 KB |
testcase_41 | AC | 640 ms
164,216 KB |
testcase_42 | AC | 639 ms
164,016 KB |
testcase_43 | AC | 622 ms
164,272 KB |
ソースコード
import sys readline = sys.stdin.readline def decomposition(Edge, st = 0): N = len(Edge) bfsorder = [st] for i in range(N): vn = bfsorder[i] for vf in Edge[vn]: Edge[vf].remove(vn) bfsorder.extend(Edge[vn]) sset = [0]*N for vn in bfsorder[::-1]: se = st = 0 for vf in Edge[vn]: st |= sset[vf]&se se |= sset[vf] tmp = ~se & -(1<<st.bit_length()) l = -tmp & tmp sset[vn] = (se|l) & -l return [(-l&l).bit_length()-1 for l in sset] MOD = 10**9+7 N = int(readline()) Edge = [[] for _ in range(N)] for _ in range(N-1): u, v, w = map(int, readline().split()) u -= 1 v -= 1 Edge[u].append((v, w)) Edge[v].append((u, w)) levels = decomposition([[e[0] for e in ei] for ei in Edge]) ans = 0 size = [0]*N ds = [0]*N ds2 = [0]*N dist = [0]*N color = [0]*N for lv in range(max(levels), 0, -1): used = [0]*N for i in range(N): if levels[i] > lv: used[i] = 1 for vn in range(N): if levels[vn] != lv: continue used[vn] = 1 dsum = 0 ssum = 0 stack = [] for vf, w in Edge[vn]: if used[vf]: continue color[vf] = vf ssum += 1 size[vf] = 1 used[vf] = 1 dist[vf] = w dsum = (dsum + w)%MOD ds[vf] = w ds2[vf]= w*w%MOD stack.append(vf) cs = stack[:] while stack: vn = stack.pop() for vf, w in Edge[vn]: if used[vf]: continue used[vf] = 1 c = color[vn] color[vf] = c dist[vf] = (dist[vn] + w)%MOD ds[c] = (ds[c] + dist[vf])%MOD dsum = (dsum + dist[vf])%MOD ds2[c] = (ds2[c] + dist[vf]*dist[vf])%MOD size[c] += 1 ssum += 1 stack.append(vf) ans = (ans + dsum*dsum)%MOD for r in cs: ans = (ans + ds2[r] + (ssum-size[r])*ds2[r] - ds[r]*ds[r])%MOD print(ans)