結果
問題 | No.416 旅行会社 |
ユーザー | TANIGUCHI Kousuke |
提出日時 | 2016-09-25 01:15:35 |
言語 | Ruby (3.3.0) |
結果 |
AC
|
実行時間 | 1,792 ms / 4,000 ms |
コード長 | 999 bytes |
コンパイル時間 | 441 ms |
コンパイル使用メモリ | 11,348 KB |
実行使用メモリ | 70,944 KB |
最終ジャッジ日時 | 2023-08-21 10:06:15 |
合計ジャッジ時間 | 19,443 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 816 ms
47,648 KB |
testcase_01 | AC | 80 ms
15,336 KB |
testcase_02 | AC | 79 ms
15,076 KB |
testcase_03 | AC | 78 ms
15,160 KB |
testcase_04 | AC | 79 ms
15,148 KB |
testcase_05 | AC | 81 ms
15,320 KB |
testcase_06 | AC | 80 ms
15,340 KB |
testcase_07 | AC | 84 ms
15,268 KB |
testcase_08 | AC | 98 ms
15,780 KB |
testcase_09 | AC | 159 ms
18,716 KB |
testcase_10 | AC | 834 ms
48,788 KB |
testcase_11 | AC | 830 ms
48,176 KB |
testcase_12 | AC | 824 ms
49,036 KB |
testcase_13 | AC | 784 ms
49,028 KB |
testcase_14 | AC | 1,770 ms
70,888 KB |
testcase_15 | AC | 1,792 ms
70,836 KB |
testcase_16 | AC | 1,707 ms
70,688 KB |
testcase_17 | AC | 1,711 ms
70,944 KB |
testcase_18 | AC | 1,724 ms
70,908 KB |
testcase_19 | AC | 1,237 ms
63,416 KB |
testcase_20 | AC | 1,254 ms
63,328 KB |
コンパイルメッセージ
Syntax OK
ソースコード
n,m,q = gets.split.map(&:to_i) F = (n + 1).times.map{|i| i } G = Array.new(n + 1){ [] } E = [] H = {} ans = Array.new(n + 1) def root(a) if F[a] == a a else F[a] = root(F[a]) end end def union(*ab) a,*b = ab.map{|i| root(i)}.sort b.each do |i| F[i] = a end end def same?(a,b) root(a) == root(b) end def bfs(s, ev, used) q = [] q << s until q.empty? v = q.shift used[v] ||= ev G[v].each do |to| q << to if !used[to] end end end m.times do |i| k = gets.chomp e = E.size a,b = k.split.map(&:to_i) E << [a, b, 2 * q] H[k] = e end (1 .. q).each do |t| k = gets.chomp e = H[k] E[e][2] = t end E.sort_by! {|(from, to, ev)| 2 * q - ev } E.each do |(from, to, ev)| union(from, to) G[from] << to G[to] << from if same?(1, from) bfs(from, ev > q ? -1 : ev, ans) end end (2 .. n).each do |i| ans[i] ||= 0 end puts ans[2 .. n]