結果
問題 | No.1582 Vertexes vs Edges |
ユーザー |
![]() |
提出日時 | 2021-07-03 09:47:41 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 6,448 bytes |
コンパイル時間 | 9,537 ms |
コンパイル使用メモリ | 295,620 KB |
実行使用メモリ | 13,952 KB |
最終ジャッジ日時 | 2024-06-30 02:44:40 |
合計ジャッジ時間 | 11,830 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
# require "/Scanner"require "io/error"class Scannerdef self.speek = STDIN.peekif not_space = peek.index { |x| x != 32 && x != 10 }if index = peek.index(not_space) { |x| x == 32 || x == 10 }result = String.new(peek[not_space...index])STDIN.skip(index + 1)resultelseresult = String.new(peek[not_space..])STDIN.skip_to_endresultendelseraise IO::EOFError.newendenddef self.is.to_iendendmacro 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 %}endendmacro 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 %}endmacro input(*types){{% for type in types %}input({{type}}),{% end %}}end# require "/graph"struct Edge(T)include Comparable(Edge(T))property to : Int32property cost : Tdef initialize(@to : Int32, @cost : T)enddef <=>(other : Edge(T)){cost, to} <=> {other.cost, other.to}enddef to_s(io) : Nilio << '(' << to << ", " << cost << ')'enddef inspect(io) : Nilio << "->#{to}(#{cost})"endendstruct Edge2(T)include Comparable(Edge2(T))property from : Int32property to : Int32property cost : Tdef initialize(@from : Int32, @to : Int32, @cost : T)enddef <=>(other : Edge2(T)){cost, from, to} <=> {other.cost, other.from, other.to}enddef reverseEdge2(T).new(to, from, cost)enddef to_s(io) : Nilio << '(' << from << ", " << to << ", " << cost << ')'enddef inspect(io) : Nilio << "#{from}->#{to}(#{cost})"endendstruct UnweightedEdge2property from : Int32property to : Int32def initialize(@from, @to)enddef reverseUnweightedEdge2.new(to, from)enddef to_s(io) : Nilio << '(' << from << ", " << to << ')'enddef inspect(io) : Nilio << "#{from}->#{to}"endendabstract 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 }enddef add_edge(i : Int32, j : Int32, cost : T)add_edge(Edge2.new(i, j, cost))enddef add_edges(edges : Array(Edge2(T)))edges.each { |edge| add_edge(edge) }selfenddelegate size, to: @graphdelegate :[], to: @graphdef each_edge : Nil(0...size).each do |v|graph[v].each do |edge|yield Edge2(T).new(v, edge.to, edge.cost)endendenddef edgesresult = [] of Edge2(T)each_edge do |edge|result << edgeendresultendendclass DirectedGraph(T) < Graph(T)def initialize(size : Int)superenddef initialize(size : Int, edges : Array(Edge2(T)))super(size)add_edges(edges)enddef add_edge(edge : Edge2(T))raise IndexError.new unless 0 <= edge.from < sizeraise IndexError.new unless 0 <= edge.to < size@graph[edge.from] << Edge.new(edge.to, edge.cost)selfendendclass UndirectedGraph(T) < Graph(T)def initialize(size : Int)superenddef initialize(size : Int, edges : Array(Edge2(T)))super(size)add_edges(edges)enddef add_edge(edge : Edge2(T))raise IndexError.new unless 0 <= edge.from < sizeraise 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)selfendendabstract class UnweightedGraphgetter 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 }enddef add_edge(i : Int32, j : Int32)add_edge(UnweightedEdge2.new(i, j))enddef add_edges(edges : Array(UnweightedEdge2))edges.each { |edge| add_edge(edge) }selfenddelegate size, to: @graphdelegate :[], to: @graphdef each_edge : Nil(0...size).each do |v|graph[v].each do |u|yield UnweightedEdge2.new(v, u)endendenddef edgesresult = [] of UnweightedEdge2each_edge do |edge|result << edgeendresultendendclass UnweightedDirectedGraph < UnweightedGraphdef initialize(size : Int)superenddef initialize(size : Int, edges : Array(UnweightedEdge2))super(size)add_edges(edges)enddef add_edge(edge : UnweightedEdge2)raise IndexError.new unless 0 <= edge.from < sizeraise IndexError.new unless 0 <= edge.to < size@graph[edge.from] << edge.toselfendendclass UnweightedUndirectedGraph < UnweightedGraphdef initialize(size : Int)superenddef initialize(size : Int, edges : Array(UnweightedEdge2))super(size)add_edges(edges)enddef add_edge(edge : UnweightedEdge2)raise IndexError.new unless 0 <= edge.from < sizeraise IndexError.new unless 0 <= edge.to < size@graph[edge.from] << edge.to@graph[edge.to] << edge.fromselfenddef each_child(vertex : Int, parent, &block) : Nilgraph[vertex].each do |u|yield u if u != parentendenddef each_child(vertex : Int, parent)graph[vertex].each.select { |u| u != parent }endendmodule Comparable(T)def max(val : T)Math.max(self, val)enddef min(val : T)Math.min(self, val)endendclass UnweightedUndirectedGraphdef solve(v, par) : {Int32, Int32}ab = each_child(v, par).map { |u| solve(u, v) }.to_ab = ab.sum(0, &.[0])a = b + (ab.max_of? { |x, y| y - x }.try(&.succ) || 0).max(0){a, b}endendn = read_line.to_iputs UnweightedUndirectedGraph.new(n, Array.new(n - 1) {i, j = read_line.split.map(&.to_i)UnweightedEdge2.new(i - 1, j - 1)}).solve(0, nil).max