結果

問題 No.19 ステージの選択
ユーザー vjudge1
提出日時 2025-09-08 10:46:03
言語 Crystal
(1.14.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,594 bytes
コンパイル時間 13,035 ms
コンパイル使用メモリ 311,356 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-09-08 10:46:18
合計ジャッジ時間 14,083 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

class DSU
  property parents_or_size : Array(Int32)

  def initialize(n : Int32)
    @parents_or_size = Array.new(n, -1)
  end

  def leader(i : Int32) : Int32
    if @parents_or_size[i] < 0
      i
    else
      @parents_or_size[i] = leader(@parents_or_size[i])
      @parents_or_size[i]
    end
  end

  def merge(a : Int32, b : Int32) : Int32
    a = leader(a)
    b = leader(b)
    return a if a == b

    if -@parents_or_size[a] < -@parents_or_size[b]
      a, b = b, a
    end
    @parents_or_size[a] += @parents_or_size[b]
    @parents_or_size[b] = a
    a
  end

  def same(a : Int32, b : Int32) : Bool
    leader(a) == leader(b)
  end

  def size(i : Int32) : Int32
    -@parents_or_size[leader(i)]
  end

  def groups : Array(Array(Int32))
    n = @parents_or_size.size
    arr = Array.new(n) { [] of Int32 }
    n.times do |i|
      arr[leader(i)] << i
    end
    arr.reject(&.empty?)
  end
end

# Main program
input = gets.not_nil!.split
n = input[0].to_i

l = Array(Int64).new(n, 0)
s = Array(Int32).new(n, 0)
ans = 0_i64

n.times do |i|
  input = gets.not_nil!.split
  l[i] = input[0].to_i64
  s[i] = input[1].to_i
  ans += l[i]
end

uf = DSU.new(n)
n.times do |i|
  uf.merge(i, s[i] - 1)
end

vis = Array.new(n, false)
grps = uf.groups

grps.each do |g|
  u = g[0]
  while !vis[u]
    vis[u] = true
    u = s[u] - 1
  end
  
  cycle = [] of Int32
  while vis[u]
    vis[u] = false
    cycle << u
    u = s[u] - 1
  end
  
  m = Int64::MAX
  cycle.each do |x|
    m = Math.min(m, l[x])
  end
  ans += m
end

if ans & 1 == 1
  puts "#{ans >> 1}.5"
else
  puts "#{ans >> 1}.0"
end
0