#679380 (Crystal) No.1607 Kth Maximum Card

提出ソース

結果

問題	No.1607 Kth Maximum Card
ユーザー	yuruhiya
提出日時	2021-07-17 14:21:54
言語	Crystal (1.11.2)
結果	AC
実行時間	575 ms / 3,500 ms
コード長	7,233 bytes
コンパイル時間	12,460 ms
コンパイル使用メモリ	293,956 KB
実行使用メモリ	29,264 KB
最終ジャッジ日時	2024-07-07 02:08:00
合計ジャッジ時間	20,651 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 ms 6,812 KB
testcase_02	AC	1 ms 6,812 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	1 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	437 ms 27,628 KB
testcase_09	AC	217 ms 25,408 KB
testcase_10	AC	428 ms 28,288 KB
testcase_11	AC	55 ms 10,112 KB
testcase_12	AC	265 ms 24,524 KB
testcase_13	AC	55 ms 7,040 KB
testcase_14	AC	67 ms 7,808 KB
testcase_15	AC	367 ms 18,676 KB
testcase_16	AC	57 ms 7,168 KB
testcase_17	AC	18 ms 6,940 KB
testcase_18	AC	209 ms 15,516 KB
testcase_19	AC	123 ms 10,752 KB
testcase_20	AC	167 ms 12,780 KB
testcase_21	AC	186 ms 13,944 KB
testcase_22	AC	532 ms 28,224 KB
testcase_23	AC	558 ms 29,264 KB
testcase_24	AC	150 ms 12,472 KB
testcase_25	AC	84 ms 9,472 KB
testcase_26	AC	110 ms 8,320 KB
testcase_27	AC	148 ms 12,672 KB
testcase_28	AC	120 ms 11,008 KB
testcase_29	AC	257 ms 20,232 KB
testcase_30	AC	575 ms 29,092 KB
testcase_31	AC	248 ms 18,476 KB
testcase_32	AC	85 ms 11,392 KB
testcase_33	AC	81 ms 11,392 KB
testcase_34	AC	89 ms 11,520 KB
testcase_35	AC	91 ms 11,392 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

結果

テストケース

ソースコード