結果
問題 | No.416 旅行会社 |
ユーザー | TANIGUCHI Kousuke |
提出日時 | 2016-09-25 01:15:35 |
言語 | Ruby (3.3.0) |
結果 |
AC
|
実行時間 | 1,980 ms / 4,000 ms |
コード長 | 999 bytes |
コンパイル時間 | 778 ms |
コンパイル使用メモリ | 7,424 KB |
実行使用メモリ | 68,320 KB |
最終ジャッジ日時 | 2024-12-14 20:18:06 |
合計ジャッジ時間 | 20,506 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 885 ms
45,760 KB |
testcase_01 | AC | 83 ms
12,288 KB |
testcase_02 | AC | 83 ms
12,160 KB |
testcase_03 | AC | 86 ms
12,160 KB |
testcase_04 | AC | 88 ms
12,160 KB |
testcase_05 | AC | 85 ms
12,288 KB |
testcase_06 | AC | 83 ms
12,160 KB |
testcase_07 | AC | 92 ms
12,416 KB |
testcase_08 | AC | 109 ms
13,056 KB |
testcase_09 | AC | 178 ms
15,680 KB |
testcase_10 | AC | 885 ms
45,760 KB |
testcase_11 | AC | 800 ms
45,852 KB |
testcase_12 | AC | 819 ms
45,764 KB |
testcase_13 | AC | 825 ms
45,728 KB |
testcase_14 | AC | 1,786 ms
68,288 KB |
testcase_15 | AC | 1,770 ms
68,044 KB |
testcase_16 | AC | 1,764 ms
68,028 KB |
testcase_17 | AC | 1,758 ms
68,320 KB |
testcase_18 | AC | 1,980 ms
68,316 KB |
testcase_19 | AC | 1,389 ms
60,696 KB |
testcase_20 | AC | 1,404 ms
60,588 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]