結果
| 問題 |
No.3291 K-step Navigation
|
| コンテスト | |
| ユーザー |
kona0001
|
| 提出日時 | 2025-08-27 05:00:31 |
| 言語 | Ruby (3.4.1) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,325 bytes |
| コンパイル時間 | 197 ms |
| コンパイル使用メモリ | 7,936 KB |
| 実行使用メモリ | 68,736 KB |
| 最終ジャッジ日時 | 2025-08-27 05:00:44 |
| 合計ジャッジ時間 | 9,020 ms |
|
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 22 TLE * 2 -- * 26 |
コンパイルメッセージ
Syntax OK
ソースコード
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
kona0001