結果

問題 No.1582 Vertexes vs Edges
ユーザー yuruhiya
提出日時 2021-07-03 10:03:22
言語 Crystal
(1.14.0)
結果
RE  
実行時間 -
コード長 6,478 bytes
コンパイル時間 15,489 ms
コンパイル使用メモリ 294,948 KB
実行使用メモリ 39,716 KB
最終ジャッジ日時 2024-06-30 02:55:58
合計ジャッジ時間 20,121 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 2 RE * 1 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

# require "/Scanner"
require "io/error"
class Scanner
def self.s
peek = STDIN.peek
if 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)
result
else
result = String.new(peek)
STDIN.skip(peek.size)
result
end
else
raise IO::EOFError.new
end
end
def self.i
s.to_i
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).max
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0