結果

問題 No.3463 Beltway
コンテスト
ユーザー tomerun
提出日時 2026-02-28 15:14:10
言語 Crystal
(1.19.1)
コンパイル:
crystal build -Donline_judge -o a.out --release --no-debug _filename_
実行:
./a.out
結果
AC  
実行時間 198 ms / 2,000 ms
コード長 1,659 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,963 ms
コンパイル使用メモリ 340,292 KB
実行使用メモリ 67,612 KB
最終ジャッジ日時 2026-02-28 15:52:21
合計ジャッジ時間 19,856 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

v, e, s, g = read_line.split.map(&.to_i)
s -= 1
g -= 1
graph = Array.new(v) { [] of Int32 }
e.times do
  a, b = read_line.split.map { |v| v.to_i - 1 }
  graph[a] << b
  graph[b] << a
end
_, bridges = lowlink(graph)
bs = Array.new(v) { Set(Int32).new }
bridges.each do |a, b|
  bs[a] << b
  bs[b] << a
end
prev = Array.new(v, -1)
q = [s]
prev[s] = s
while q.size > 0 && prev[g] == -1
  nq = [] of Int32
  q.each do |cur|
    graph[cur].each do |adj|
      next if prev[adj] != -1
      prev[adj] = cur
      nq << adj
    end
  end
  q = nq
end
if prev[g] == -1
  puts -1
  exit
end
ans = 0
cur = g
while cur != s
  p = prev[cur]
  if !bs[cur].includes?(p)
    ans += 1
  end
  cur = p
end
puts ans

def lowlink(g : Array(Array(Int32))) : Tuple(Set(Int32), Array(Tuple(Int32, Int32)))
  ord = Array.new(g.size, -1)
  low = Array.new(g.size, g.size)
  cnt_child = Array.new(g.size, 0)
  articulations = Set(Int32).new
  bridges = [] of Tuple(Int32, Int32)
  dfs = uninitialized Int32, Int32, Int32 -> Int32
  dfs = ->(cur : Int32, idx : Int32, prev : Int32) do
    ord[cur] = idx
    low[cur] = idx
    idx += 1
    g[cur].each do |adj|
      next if adj == prev
      if ord[adj] == -1
        idx = dfs.call(adj, idx, cur)
        cnt_child[cur] += 1
        low[cur] = {low[cur], low[adj]}.min
        if ord[cur] < low[adj]
          bridges << {cur, adj}
        end
        if cur != 0 && ord[cur] <= low[adj]
          articulations << cur
        end
      else
        low[cur] = {low[cur], ord[adj]}.min
      end
    end
    return idx
  end
  dfs.call(0, 0, -1)
  if cnt_child[0] > 1
    articulations << 0
  end
  return articulations, bridges
end
0