#671383 (Crystal) No.1576 織姫と彦星

提出ソース

結果

問題	No.1576 織姫と彦星
ユーザー	yuruhiya
提出日時	2021-06-29 20:29:12
言語	Crystal (1.11.2)
結果	AC
実行時間	4 ms / 2,000 ms
コード長	5,767 bytes
コンパイル時間	20,971 ms
コンパイル使用メモリ	257,672 KB
実行使用メモリ	4,836 KB
最終ジャッジ日時	2023-09-08 05:41:09
合計ジャッジ時間	20,808 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,420 KB
testcase_01	AC	3 ms 4,500 KB
testcase_02	AC	3 ms 4,488 KB
testcase_03	AC	2 ms 4,424 KB
testcase_04	AC	2 ms 4,504 KB
testcase_05	AC	3 ms 4,468 KB
testcase_06	AC	2 ms 4,556 KB
testcase_07	AC	3 ms 4,540 KB
testcase_08	AC	3 ms 4,656 KB
testcase_09	AC	2 ms 4,560 KB
testcase_10	AC	4 ms 4,664 KB
testcase_11	AC	3 ms 4,492 KB
testcase_12	AC	3 ms 4,688 KB
testcase_13	AC	4 ms 4,728 KB
testcase_14	AC	4 ms 4,648 KB
testcase_15	AC	3 ms 4,644 KB
testcase_16	AC	3 ms 4,544 KB
testcase_17	AC	4 ms 4,772 KB
testcase_18	AC	3 ms 4,552 KB
testcase_19	AC	3 ms 4,556 KB
testcase_20	AC	4 ms 4,616 KB
testcase_21	AC	3 ms 4,740 KB
testcase_22	AC	3 ms 4,740 KB
testcase_23	AC	2 ms 4,456 KB
testcase_24	AC	3 ms 4,596 KB
testcase_25	AC	4 ms 4,708 KB
testcase_26	AC	4 ms 4,668 KB
testcase_27	AC	3 ms 4,620 KB
testcase_28	AC	4 ms 4,648 KB
testcase_29	AC	3 ms 4,708 KB
testcase_30	AC	2 ms 4,468 KB
testcase_31	AC	3 ms 4,656 KB
testcase_32	AC	3 ms 4,628 KB
testcase_33	AC	4 ms 4,836 KB
testcase_34	AC	3 ms 4,564 KB
testcase_35	AC	3 ms 4,608 KB
testcase_36	AC	3 ms 4,492 KB
testcase_37	AC	3 ms 4,692 KB
testcase_38	AC	3 ms 4,616 KB
testcase_39	AC	3 ms 4,620 KB
testcase_40	AC	3 ms 4,680 KB
testcase_41	AC	3 ms 4,532 KB
testcase_42	AC	3 ms 4,520 KB
testcase_43	AC	3 ms 4,552 KB
testcase_44	AC	4 ms 4,832 KB
testcase_45	AC	3 ms 4,572 KB
testcase_46	AC	4 ms 4,576 KB
testcase_47	AC	2 ms 4,684 KB
testcase_48	AC	3 ms 4,624 KB
testcase_49	AC	3 ms 4,716 KB
testcase_50	AC	3 ms 4,508 KB
testcase_51	AC	3 ms 4,480 KB
testcase_52	AC	4 ms 4,660 KB
testcase_53	AC	3 ms 4,704 KB
testcase_54	AC	4 ms 4,640 KB
testcase_55	AC	4 ms 4,672 KB
testcase_56	AC	3 ms 4,648 KB
testcase_57	AC	3 ms 4,472 KB
testcase_58	AC	3 ms 4,568 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

# require "/graph/bfs"
# require "./graph"
struct Edge(T)
  include Comparable(Edge(T))

  property to : Int32
  property cost : T

  def initialize(@to : Int32, @cost : T)
  end

  def <=>(other : Edge(T))
    {cost, to} <=> {other.cost, other.to}
  end

  def to_s(io) : Nil
    io << '(' << to << ", " << cost << ')'
  end

  def inspect(io) : Nil
    io << "->#{to}(#{cost})"
  end
end

struct Edge2(T)
  include Comparable(Edge2(T))

  property from : Int32
  property to : Int32
  property cost : T

  def initialize(@from : Int32, @to : Int32, @cost : T)
  end

  def <=>(other : Edge2(T))
    {cost, from, to} <=> {other.cost, other.from, other.to}
  end

  def reverse
    Edge2(T).new(to, from, cost)
  end

  def to_s(io) : Nil
    io << '(' << from << ", " << to << ", " << cost << ')'
  end

  def inspect(io) : Nil
    io << "#{from}->#{to}(#{cost})"
  end
end

struct UnweightedEdge2
  property from : Int32
  property to : Int32

  def initialize(@from, @to)
  end

  def reverse
    UnweightedEdge2.new(to, from)
  end

  def to_s(io) : Nil
    io << '(' << from << ", " << to << ')'
  end

  def inspect(io) : Nil
    io << "#{from}->#{to}"
  end
end

abstract class Graph(T)
  getter graph : Array(Array(Edge(T)))

  def initialize(size : Int)
    raise ArgumentError.new("Negative graph size: #{size}") unless size >= 0
    @graph = Array.new(size) { Array(Edge(T)).new }
  end

  def add_edge(i : Int32, j : Int32, cost : T)
    add_edge(Edge2.new(i, j, cost))
  end

  def add_edges(edges : Array(Edge2(T)))
    edges.each { |edge| add_edge(edge) }
    self
  end

  delegate size, to: @graph
  delegate :[], to: @graph

  def each_edge : Nil
    (0...size).each do |v|
      graph[v].each do |edge|
        yield Edge2(T).new(v, edge.to, edge.cost)
      end
    end
  end

  def edges
    result = [] of Edge2(T)
    each_edge do |edge|
      result << edge
    end
    result
  end
end

class DirectedGraph(T) < Graph(T)
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Array(Edge2(T)))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : Edge2(T))
    raise IndexError.new unless 0 <= edge.from < size
    raise IndexError.new unless 0 <= edge.to < size
    @graph[edge.from] << Edge.new(edge.to, edge.cost)
    self
  end
end

class UndirectedGraph(T) < Graph(T)
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Array(Edge2(T)))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : Edge2(T))
    raise IndexError.new unless 0 <= edge.from < size
    raise IndexError.new unless 0 <= edge.to < size
    @graph[edge.from] << Edge.new(edge.to, edge.cost)
    @graph[edge.to] << Edge.new(edge.from, edge.cost)
    self
  end
end

abstract class UnweightedGraph
  getter graph : Array(Array(Int32))

  def initialize(size : Int)
    raise ArgumentError.new("Negative graph size: #{size}") unless size >= 0
    @graph = Array.new(size) { Array(Int32).new }
  end

  def add_edge(i : Int32, j : Int32)
    add_edge(UnweightedEdge2.new(i, j))
  end

  def add_edges(edges : Array(UnweightedEdge2))
    edges.each { |edge| add_edge(edge) }
    self
  end

  delegate size, to: @graph
  delegate :[], to: @graph

  def each_edge : Nil
    (0...size).each do |v|
      graph[v].each do |u|
        yield UnweightedEdge2.new(v, u)
      end
    end
  end

  def edges
    result = [] of UnweightedEdge2
    each_edge do |edge|
      result << edge
    end
    result
  end
end

class UnweightedDirectedGraph < UnweightedGraph
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Array(UnweightedEdge2))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : UnweightedEdge2)
    raise IndexError.new unless 0 <= edge.from < size
    raise IndexError.new unless 0 <= edge.to < size
    @graph[edge.from] << edge.to
    self
  end
end

class UnweightedUndirectedGraph < UnweightedGraph
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Array(UnweightedEdge2))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : UnweightedEdge2)
    raise IndexError.new unless 0 <= edge.from < size
    raise IndexError.new unless 0 <= edge.to < size
    @graph[edge.from] << edge.to
    @graph[edge.to] << edge.from
    self
  end

  def each_child(vertex : Int, parent)
    graph[vertex].each do |u|
      yield u if u != parent
    end
  end
end

class UnweightedGraph
  def bfs(start : Int32, unreachable : U = nil) forall U
    raise ArgumentError.new unless 0 <= start < size
    queue = Deque{start}
    dist = Array(Int32?).new(size, nil)
    dist[start] = 0
    while v = queue.pop?
      graph[v].each do |edge|
        if dist[edge].nil?
          dist[edge] = dist[v].not_nil! + 1
          queue.unshift edge
        end
      end
    end
    dist.map { |i| i || unreachable }
  end

  def bfs!(start : Int32)
    bfs(start).map(&.not_nil!)
  end

  def bfs_st(start : Int32, goal : Int32, unreachable : U = nil) forall U
    raise ArgumentError.new unless 0 <= start < size
    queue = Deque{start}
    dist = Array(Int32?).new(size, nil)
    dist[start] = 0
    while v = queue.pop?
      d = dist[v].not_nil!
      return d if v == goal
      graph[v].each do |edge|
        if dist[edge].nil?
          dist[edge] = d + 1
          queue.unshift edge
        end
      end
    end
    unreachable
  end
end

n = read_line.to_i
s, t = read_line.split.map(&.to_i)
a = read_line.split.map(&.to_i)
stones = a + [s, t]
hash = stones.zip(0..).to_h
g = UnweightedUndirectedGraph.new(stones.size)
stones.each_with_index do |x, i|
  (0..30).each do |bit|
    if j = hash[x ^ (1 << bit)]?
      g.add_edge(i, j)
    end
  end
end
puts g.bfs_st(hash[s], hash[t]).try(&.pred) || -1

yukicoder

結果

テストケース

ソースコード