結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー |
![]() |
提出日時 | 2021-08-19 15:56:37 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 109 ms / 2,500 ms |
コード長 | 850 bytes |
コンパイル時間 | 10,333 ms |
コンパイル使用メモリ | 297,056 KB |
実行使用メモリ | 33,152 KB |
最終ジャッジ日時 | 2024-10-13 03:32:53 |
合計ジャッジ時間 | 17,037 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
class Solve def initialize h, w, n = read_line.split.map(&.to_i) @xy = Array(Array(Int32)).new(n) { read_line.split.map(&.to_i.pred) } @graph = Array(Array({Int32, Int32})).new(h + w) { [] of {Int32, Int32} } @xy.each_with_index do |(x, y), i| @graph[x] << {h + y, i} @graph[h + y] << {x, i} end @cycle = [] of Int32 @index = Array(Int32?).new(h + w, nil) end def dfs(v, p) if i = @index[v] ans = @cycle[i..] ans.rotate! if @xy[ans[0]][1] != @xy[ans[1]][1] puts ans.size, ans.join(' ', &.succ) exit end @index[v] = @cycle.size @graph[v].each do |u, i| next if u == p @cycle.push i dfs(u, v) @cycle.pop end end def solve @graph.size.times do |i| dfs(i, p) if @index[i].nil? end puts -1 end end Solve.new.solve