結果
問題 |
No.3291 K-step Navigation
|
ユーザー |
![]() |
提出日時 | 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