結果
問題 | No.872 All Tree Path |
ユーザー | TANIGUCHI Kousuke |
提出日時 | 2019-12-10 12:47:38 |
言語 | Ruby (3.3.0) |
結果 |
AC
|
実行時間 | 1,415 ms / 3,000 ms |
コード長 | 678 bytes |
コンパイル時間 | 355 ms |
コンパイル使用メモリ | 11,192 KB |
実行使用メモリ | 80,140 KB |
最終ジャッジ日時 | 2023-09-06 06:38:06 |
合計ジャッジ時間 | 15,066 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,388 ms
79,152 KB |
testcase_01 | AC | 1,387 ms
79,448 KB |
testcase_02 | AC | 1,378 ms
80,140 KB |
testcase_03 | AC | 1,015 ms
74,620 KB |
testcase_04 | AC | 81 ms
15,176 KB |
testcase_05 | AC | 1,404 ms
78,820 KB |
testcase_06 | AC | 1,402 ms
79,068 KB |
testcase_07 | AC | 1,415 ms
78,880 KB |
testcase_08 | AC | 181 ms
20,448 KB |
testcase_09 | AC | 179 ms
20,748 KB |
testcase_10 | AC | 175 ms
20,560 KB |
testcase_11 | AC | 182 ms
20,800 KB |
testcase_12 | AC | 183 ms
20,708 KB |
testcase_13 | AC | 81 ms
15,308 KB |
testcase_14 | AC | 82 ms
15,024 KB |
testcase_15 | AC | 83 ms
15,160 KB |
testcase_16 | AC | 82 ms
15,060 KB |
testcase_17 | AC | 81 ms
15,120 KB |
testcase_18 | AC | 80 ms
15,264 KB |
testcase_19 | AC | 81 ms
15,020 KB |
コンパイルメッセージ
Syntax OK
ソースコード
Edge = Struct.new(:from, :to, :weight) N = gets.to_i G = Array.new(N + 1){ [] } T = Array.new(N + 1){ [] } # tree as root was 1 C = Array.new(N + 1) # node count of subtree (1 ... N).each do u,v,w = gets.split.map(&:to_i) G[u] << Edge.new(u, v, w) G[v] << Edge.new(v, u, w) end used = Array.new(N + 1) stack = [1] used[1] = true order = [] until stack.empty? u = stack.pop order << u G[u].each do |e| unless used[e.to] used[e.to] = true stack << e.to T[u] << e end end end order.reverse_each{|u| C[u] = T[u].inject(1){|c, e| c + C[e.to] } } ans = T.flatten.inject(0){|s, e| s + e.weight * C[e.to] * (N - C[e.to]) * 2} puts ans