結果
問題 | No.1519 Diversity |
ユーザー |
![]() |
提出日時 | 2021-05-28 21:29:50 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 5,083 bytes |
コンパイル時間 | 14,430 ms |
コンパイル使用メモリ | 294,924 KB |
実行使用メモリ | 11,336 KB |
最終ジャッジ日時 | 2024-11-07 09:02:16 |
合計ジャッジ時間 | 14,392 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 15 |
ソースコード
# 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 }endabstract def add_edge(edge : Edge2(T))abstract def add_edges(edges : Array(Edge2(T)))def add_edge(i : Int32, j : Int32, cost : T)add_edge(Edge2.new(i, j, cost))enddelegate 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 edges : Array(Edge2(T))result = [] 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)selfenddef add_edges(edges : Array(Edge2(T)))edges.each { |edge| add_edge(edge) }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)selfenddef add_edges(edges : Array(Edge2(T)))edges.each { |edge| add_edge(edge) }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 }endabstract def add_edge(edge : UnweightedEdge2)abstract def add_edges(edges : Array(UnweightedEdge2))def add_edge(i : Int32, j : Int32)add_edge(UnweightedEdge2.new(i, j))enddelegate size, to: @graphdelegate :[], to: @graphdef each_edge : Nil(0...size).each do |v|graph[v].each do |u|yield UnweightedEdge2.new(v, u)endendenddef edges : Array(UnweightedEdge2)result = [] 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.toselfenddef add_edges(edges : Array(UnweightedEdge2))edges.each { |edge| add_edge(edge) }selfendendclass 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 add_edges(edges : Array(UnweightedEdge2))edges.each { |edge| add_edge(edge) }selfendendn = read_line.to_ig = UnweightedUndirectedGraph.new(n)(1...n).reverse_each do |i|v = 0while g[i].size < iif v == 0g.add_edge(i, v)v = i - 1elseg.add_edge(i, v)v = v - 1endendendputs g.edges.size // 2puts g.edges.select { |e| e.from < e.to }.join('\n') { |e|"#{e.from + 1} #{e.to + 1}"}