#679380 (Crystal) No.1607 Kth Maximum Card

提出ソース

結果

問題	No.1607 Kth Maximum Card
ユーザー	yuruhiya
提出日時	2021-07-17 14:21:54
言語	Crystal (1.11.2)
結果	AC
実行時間	982 ms / 3,500 ms
コード長	7,233 bytes
コンパイル時間	20,854 ms
コンパイル使用メモリ	254,432 KB
実行使用メモリ	34,480 KB
最終ジャッジ日時	2023-09-21 07:43:32
合計ジャッジ時間	32,926 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 4,328 KB
testcase_01	AC	3 ms 4,360 KB
testcase_02	AC	3 ms 4,408 KB
testcase_03	AC	2 ms 4,452 KB
testcase_04	AC	2 ms 4,420 KB
testcase_05	AC	2 ms 4,432 KB
testcase_06	AC	3 ms 4,432 KB
testcase_07	AC	3 ms 4,360 KB
testcase_08	AC	555 ms 32,192 KB
testcase_09	AC	311 ms 29,124 KB
testcase_10	AC	654 ms 32,312 KB
testcase_11	AC	54 ms 11,032 KB
testcase_12	AC	361 ms 28,012 KB
testcase_13	AC	60 ms 8,596 KB
testcase_14	AC	73 ms 9,300 KB
testcase_15	AC	480 ms 23,724 KB
testcase_16	AC	59 ms 8,336 KB
testcase_17	AC	18 ms 6,336 KB
testcase_18	AC	244 ms 17,108 KB
testcase_19	AC	137 ms 13,332 KB
testcase_20	AC	190 ms 15,872 KB
testcase_21	AC	217 ms 16,608 KB
testcase_22	AC	828 ms 34,352 KB
testcase_23	AC	841 ms 34,480 KB
testcase_24	AC	151 ms 15,164 KB
testcase_25	AC	88 ms 10,388 KB
testcase_26	AC	114 ms 10,764 KB
testcase_27	AC	184 ms 15,512 KB
testcase_28	AC	132 ms 11,628 KB
testcase_29	AC	363 ms 21,824 KB
testcase_30	AC	982 ms 33,064 KB
testcase_31	AC	355 ms 21,972 KB
testcase_32	AC	80 ms 13,164 KB
testcase_33	AC	79 ms 13,092 KB
testcase_34	AC	84 ms 13,192 KB
testcase_35	AC	85 ms 13,296 KB

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

ソースコード

raw source code

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

  property to : Int32, 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, to : Int32, 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 sort
    Edge2(T).new(*{to, from}.minmax, 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, to : Int32

  def initialize(@from, @to)
  end

  def reverse
    UnweightedEdge2.new(to, from)
  end

  def sort
    UnweightedEdge2.new(*{to, from}.minmax)
  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(from : Int, to : Int, cost : T)
    add_edge(Edge2.new(from, to, cost))
  end

  def add_edge(from_to_cost : {Int32, Int32, T})
    add_edge(Edge2.new(*from_to_cost))
  end

  def add_edges(edges)
    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

  def reverse
    result = self.class.new(size)
    each_edge do |edge|
      result.add_edge(edge.reverse)
    end
    result
  end
end

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

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

  def initialize(size : Int, edges : Enumerable({Int32, Int32, T}))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : Edge2(T))
    raise IndexError.new unless 0 <= edge.from < size && 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 : Enumerable(Edge2(T)))
    super(size)
    add_edges(edges)
  end

  def initialize(size : Int, edges : Enumerable({Int32, Int32, T}))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : Edge2(T))
    raise IndexError.new unless 0 <= edge.from < size && 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(from : Int, to : Int)
    add_edge(UnweightedEdge2.new(from, to))
  end

  def add_edge(from_to : {Int32, Int32})
    add_edge(*from_to)
  end

  def add_edges(edges)
    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

  def reverse
    result = self.class.new(size)
    each_edge do |edge|
      result.add_edge(edge.reverse)
    end
    result
  end
end

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

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

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

  def to_undirected : self
    result = UnweightedDirectedGraph.new(size)
    each_edge do |edge|
      result.add_edge(edge)
      result.add_edge(edge.reverse)
    end
    result
  end
end

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

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

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

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

  def each_child(vertex : Int, parent)
    graph[vertex].each.select { |u| u != parent }
  end

  def to_undirected : self
    self
  end
end

class Graph(T)
  def bfs01(start : Int, &block)
    raise ArgumentError.new unless 0 <= start < size
    queue = Deque{start}
    dist = Array(Int32?).new(size, nil)
    dist[start] = 0
    while v = queue.shift?
      current_dist = dist[v].not_nil!
      graph[v].each do |edge|
        cost = yield(edge)
        raise ArgumentError.new("Unexpected cost: #{cost}") unless cost == 0 || cost == 1
        next_dist = current_dist + cost
        if (d = dist[edge.to]).nil? || next_dist < d
          dist[edge.to] = next_dist
          if cost == 0
            que.unshift edge.to
          else
            que.push edge.to
          end
        end
      end
    end
    dist
  end

  def bfs01(start : Int)
    bfs01(start, &.cost)
  end

  def bfs01!(start : Int32, &block)
    bfs01(start) { |edge| yield edge }.map(&.not_nil!)
  end

  def bfs01!(start : Int)
    bfs01!(start, &.cost)
  end

  def bfs01_st(start : Int, goal : Int) : Int32?
    raise ArgumentError.new unless 0 <= start < size
    queue = Deque{start}
    dist = Array(Int32?).new(size, nil)
    dist[start] = 0
    while v = queue.shift?
      current_dist = dist[v].not_nil!
      return current_dist if v == goal
      graph[v].each do |edge|
        cost = yield(edge)
        raise ArgumentError.new("Unexpected cost: #{cost}") unless cost == 0 || cost == 1
        next_dist = current_dist + cost
        if (d = dist[edge.to]).nil? || next_dist < d
          dist[edge.to] = next_dist
          if cost == 0
            queue.unshift edge.to
          else
            queue.push edge.to
          end
        end
      end
    end
    nil
  end
end

n, m, k = read_line.split.map(&.to_i)
graph = UndirectedGraph.new n, Array.new(m) {
  u, v, c = read_line.split.map(&.to_i)
  {u - 1, v - 1, c}
}
puts (0..2*10**5).bsearch { |x|
  graph.bfs01_st(0, n - 1) { |edge|
    edge.cost > x ? 1 : 0
  }.not_nil! < k
}

yukicoder

結果

テストケース

ソースコード