結果

問題 No.3291 K-step Navigation
コンテスト
ユーザー kona0001
提出日時 2025-08-27 05:02:31
言語 Ruby
(3.4.1)
結果
AC  
実行時間 1,991 ms / 3,000 ms
コード長 1,325 bytes
コンパイル時間 411 ms
コンパイル使用メモリ 8,064 KB
実行使用メモリ 62,848 KB
最終ジャッジ日時 2025-10-03 23:29:56
合計ジャッジ時間 20,795 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 51
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

def assert f
  unless f
    puts "Error!: Constraint Violation"
    exit
  end
end

n,m,k,s,t = gets.split.map(&:to_i)
assert(2 <= n && n <= 3000)
max_m = [3000, n*(n-1)/2].min
assert(0 <= m && m <= max_m)
assert(1 <= k && k <= 10**18)
assert(1 <= s && s <= n)
assert(1 <= t && t <= n)
assert(s != t)
s,t = [s,t].sort

g = Array.new(n+1){Array.new}
hash = {}
st_flg = false
ok_flg = false
m.times do
  u,v = gets.split.map(&:to_i)
  assert(1 <= u && u < v && v <= n)
  assert(hash[[u,v]] == nil)
  hash[[u,v]] = 1
  g[u] << v
  g[v] << u
  if u == s && v == t
    st_flg = true
  elsif u == s || u == t || v == s || v == t
    ok_flg = true
  end
end

if ok_flg
  puts "Yes"
  exit
end

unless st_flg
  if k%2 == 1
    puts "Yes"
  else
    puts "No"
  end
  exit
end

if k%2 == 1
  puts "Yes"
  exit
end

# s-t が連結で孤立しており、Kが偶数の場合
inf = 10**18
min_odd_cycle = inf
1.upto(n) do |i|
  dist = Array.new(n+1,-1)
  dist[i] = 0
  queue = [i]
  while v = queue.shift
    g[v].each do |to|
      if dist[to] != -1 && dist[v]%2 == dist[to]%2
        min_odd_cycle = [min_odd_cycle, dist[v] + dist[to] + 1].min
      elsif dist[to] == -1
        dist[to] = dist[v] + 1
        queue << to
      end
    end
  end
end

if min_odd_cycle == inf || min_odd_cycle + 3 > k
  puts "No"
else
  puts "Yes"
end
0