結果
問題 | No.1507 Road Blocked |
ユーザー |
![]() |
提出日時 | 2021-05-15 18:20:50 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 6,024 bytes |
コンパイル時間 | 13,880 ms |
コンパイル使用メモリ | 295,220 KB |
実行使用メモリ | 22,740 KB |
最終ジャッジ日時 | 2024-10-03 05:43:11 |
合計ジャッジ時間 | 17,894 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
# require "template"lib Cfun strtoll(s : UInt8*, p : UInt8**, b : Int32) : Int64endclass Stringdef to_i64C.strtoll(self, nil, 10)endend# require "graph/tree"# 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})"endendclass Graph(T)getter graph : Array(Array(Edge(T)))def initialize(size : Int32)raise ArgumentError.new("Negative graph size: #{size}") unless size >= 0@graph = Array.new(size) { Array(Edge(T)).new }enddef initialize(size, edges : Array(Edge2(T)), *, undirected : Bool)raise ArgumentError.new("Negative graph size: #{size}") unless size >= 0@graph = Array.new(size) { Array(Edge(T)).new }edges.each do |edge|@graph[edge.from] << Edge.new(edge.to, edge.cost)@graph[edge.to] << Edge.new(edge.from, edge.cost) if undirectedendenddef add_edge(i : Int32, j : Int32, cost : T)raise IndexError.new unless 0 <= i < sizeraise IndexError.new unless 0 <= j < sizegraph[i] << Edge(T).new(j, cost)graph[j] << Edge(T).new(i, cost)enddef add_edge_directed(i : Int32, j : Int32, cost : T)raise IndexError.new unless 0 <= i < sizeraise IndexError.new unless 0 <= j < sizegraph[i] << Edge(T).new(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 each_edge(v : Int32) : Nilgraph[v].each do |edge|yield Edge2(T).new(v, edge.to, edge.cost)endenddef edges : Array(Edge2(T))result = [] of Edge2(T)each_edge do |edge|result << edgeendresultenddef edges(v : Int32) : Array(Edge2(T))result = [] of Edge2(T)each_edge(v) do |edge|result << edgeendresultendendstruct UnWeightedEdgeproperty from : Int32property to : Int32def initialize(@from, @to)endendclass UnWeightedGraphgetter size : Int32getter graph : Array(Array(Int32))def initialize(@size)raise ArgumentError.new("Negative graph size: #{size}") unless size >= 0@graph = Array.new(size) { Array(Int32).new }enddef initialize(@size, edges : Array(UnWeightedEdge), *, undirected : Bool)raise ArgumentError.new("Negative graph size: #{size}") unless size >= 0@graph = Array.new(size) { Array(Int32).new }edges.each do |edge|@graph[edge.from] << edge.to@graph[edge.to] << edge.from if undirectedendenddelegate size, to: @graphdelegate :[], to: @graphdef add_edge(i : Int32, j : Int32)raise IndexError.new unless 0 <= i < sizeraise IndexError.new unless 0 <= j < sizegraph[i] << jgraph[j] << ienddef add_edge_directed(i : Int32, j : Int32)raise IndexError.new unless 0 <= i < sizeraise IndexError.new unless 0 <= j < sizegraph[i] << jendendclass UnWeightedGraphdef subtree_size_dfs(v : Int32, p : Int32, result : Array(Int32)) : Int32result[v] = 1 + self[v].select { |u| u != p }.sum { |u|subtree_size_dfs(u, v, result)}enddef subtree_size(root : Int32)result = Array.new(size, 0)subtree_size_dfs(root, -1, result)resultendendstruct Mint@@MOD = 998244353i64def self.mod@@MODenddef self.zeroMint.newend@value : Int64def initialize@value = 0i64enddef initialize(value)@value = value.to_i64 % @@MODenddef initialize(m : Mint)@value = m.valueendprotected def value=(value : Int64)@value = valueendgetter value : Int64def + : selfselfenddef - : selfMint.new(value != 0 ? @@MOD - @value : 0)enddef +(m)self + m.to_mintenddef +(m : Mint)result = Mint.newresult.value = @value + m.valueresult.value -= @@MOD if result.value >= @@MODresultenddef -(m)self - m.to_mintenddef -(m : Mint)result = Mint.newresult.value = @value - m.valueresult.value += @@MOD if result.value < 0resultenddef *(m)result = Mint.newresult.value = @value * Mint.new(m).value % @@MODresultenddef /(m)raise DivisionByZeroError.new if m == 0a, b, u, v = m.to_i64, @@MOD, 1i64, 0i64while b != 0t = a // ba -= t * ba, b = b, au -= t * vu, v = v, uendMint.new(@value * u)enddef //(m)self / menddef **(m : Int)t, res = self, Mint.new(1)while m > 0res *= t if m.odd?t *= tm >>= 1endresenddef ==(m)@value == m.to_i64enddef !=(m)@value != m.to_i64enddef succself + 1enddef predself - 1enddef to_i64 : Int64@valueenddelegate to_s, to: @valuedelegate inspect, to: @valueendstruct Intdef to_mint : MintMint.new(self)endendclass Stringdef to_mint : MintMint.new(self)endendn = read_line.to_im = Mint.new(n.to_i64 * ~-n // 2)g = UnWeightedGraph.new n, (1..n - 1).map {a, b = read_line.split.map &.to_i.predUnWeightedEdge.new(a, b)}, undirected: trueputs g.subtree_size(0)[1..].sum { |size|size2 = Mint.new(size.to_i64 * (n - size))(m - size2) / m} / n.pred