#672828 (Crystal) No.1582 Vertexes vs Edges

提出ソース

結果

問題	No.1582 Vertexes vs Edges
ユーザー	yuruhiya
提出日時	2021-07-03 11:14:52
言語	Crystal (1.11.2)
結果	AC
実行時間	64 ms / 2,000 ms
コード長	6,714 bytes
コンパイル時間	12,881 ms
コンパイル使用メモリ	295,224 KB
実行使用メモリ	14,064 KB
最終ジャッジ日時	2024-06-30 03:29:08
合計ジャッジ時間	15,127 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	4 ms 5,376 KB
testcase_05	AC	45 ms 12,928 KB
testcase_06	AC	4 ms 5,376 KB
testcase_07	AC	8 ms 5,376 KB
testcase_08	AC	23 ms 8,448 KB
testcase_09	AC	41 ms 12,544 KB
testcase_10	AC	27 ms 9,344 KB
testcase_11	AC	5 ms 5,376 KB
testcase_12	AC	19 ms 7,680 KB
testcase_13	AC	34 ms 9,728 KB
testcase_14	AC	34 ms 9,728 KB
testcase_15	AC	45 ms 11,776 KB
testcase_16	AC	23 ms 7,808 KB
testcase_17	AC	32 ms 9,472 KB
testcase_18	AC	52 ms 13,440 KB
testcase_19	AC	32 ms 9,984 KB
testcase_20	AC	31 ms 9,088 KB
testcase_21	AC	26 ms 8,704 KB
testcase_22	AC	49 ms 12,416 KB
testcase_23	AC	19 ms 6,016 KB
testcase_24	AC	10 ms 5,376 KB
testcase_25	AC	26 ms 8,448 KB
testcase_26	AC	21 ms 7,424 KB
testcase_27	AC	48 ms 11,648 KB
testcase_28	AC	15 ms 5,504 KB
testcase_29	AC	39 ms 10,496 KB
testcase_30	AC	25 ms 8,064 KB
testcase_31	AC	40 ms 10,624 KB
testcase_32	AC	18 ms 6,016 KB
testcase_33	AC	64 ms 14,064 KB
testcase_34	AC	60 ms 13,952 KB
testcase_35	AC	62 ms 13,952 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	1 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB

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

ソースコード

raw source code

# require "/Scanner"
require "io/error"

class Scanner
  def self.s
    peek = STDIN.peek
    not_space = peek.index { |x| x != 32 && x != 10 } || peek.size
    STDIN.skip(not_space)
    peek += not_space

    if index = peek.index { |x| x == 32 || x == 10 }
      STDIN.skip(index + 1)
      return String.new(peek[0, index])
    end

    String.build do |buffer|
      loop do
        buffer.write peek
        STDIN.skip(peek.size)
        peek = STDIN.peek
        break if peek.empty?
        if index = peek.index { |x| x == 32 || x == 10 }
          buffer.write peek[0, index]
          STDIN.skip(index)
          break
        end
      end
    end
  end

  def self.i
    s.to_i
  end

  def self.i64
    s.to_i64
  end
end

macro input_array(type, args)
  Array.new({{args.first}}) do
    {% if args.size == 1 %}
      input({{type.id}})
    {% else %}
      input_array({{type}}, {{args[1...args.size]}})
    {% end %}
  end
end

macro input(type)
  {% if type.is_a?(Path) %}
    {{type}}.new(Scanner.s)
  {% elsif type.is_a?(Var) %}
    {% if Scanner.methods.includes?(type.id) %}
      Scanner.{{type.id}}
    {% else %}
      Scanner.s.to_{{type.id}}
    {% end %}
  {% elsif type.is_a?(Call) && type.args.size == 0 %}
    {% if Scanner.methods.includes?(type) %}
      Scanner.{{type.id}}
    {% else %}
      Scanner.s.to_{{type.id}}
    {% end %}
  {% elsif type.name == "[]" %}
    input_array("{{type.receiver}}", {{type.args}})
  {% else %}
    input_array("{{type.name}}", {{type.args}})
  {% end %}
end

macro input(*types)
  {
    {% for type in types %}
      input({{type}}),
    {% end %}
  }
end

# 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, &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
end

module Comparable(T)
  def max(val : T)
    Math.max(self, val)
  end

  def max0
    Math.max(self, typeof(self).zero)
  end

  def min(val : T)
    Math.min(self, val)
  end
end

class UnweightedUndirectedGraph
  def solve(v, par) : {Int32, Int32}
    ab = each_child(v, par).map { |u| solve(u, v) }.to_a
    b = ab.sum(0, &.[0])
    a = b + (ab.max_of? { |x, y| y - x }.try(&.succ) || 0).max0
    {a, b}
  end
end

n = input(i)
puts UnweightedUndirectedGraph.new(n, Array.new(n - 1) { |time|
  i, j = input(i, i)
  UnweightedEdge2.new(i - 1, j - 1)
}).solve(0, nil)[0]

yukicoder

結果

テストケース

ソースコード