結果
問題 | No.1553 Lovely City |
ユーザー |
![]() |
提出日時 | 2021-07-21 18:47:07 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 600 ms / 2,000 ms |
コード長 | 14,986 bytes |
コンパイル時間 | 13,632 ms |
コンパイル使用メモリ | 302,400 KB |
実行使用メモリ | 98,864 KB |
最終ジャッジ日時 | 2024-07-17 14:14:57 |
合計ジャッジ時間 | 26,838 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
# require "/scanner"# ### Specifications## ```plain# Inside input macro | Expanded code# ----------------------------------------------+---------------------------------------# Uppercase string: Int32, Int64, Float64, etc. | {}.new(Scanner.s)# s | Scanner.s# c | Scanner.c# Other lowercase string: i, i64, f, etc. | Scanner.s.to_{}# operator[]: type[size] | Array.new(input(size)) { input(type) }# Tuple literal: {t1, t2, t3} | {input(t1), input(t2), input(t3)}# Array literal: [t1, t2, t3] | [input(t1), input(t2), input(t3)]# Range literal: t1..t2 | input(t1)..input(t2)# If: cond ? t1 : t2 | cond ? input(t1) : input(t2)# Assign: target = value | target = input(value)# ```## ### Examples## Input:# ```plain# 5 3# foo bar# 1 2 3 4 5# ```# ```# n, m = input(Int32, Int64) # => {5, 10i64}# input(String, Char[m]) # => {"foo", ['b', 'a', 'r']}# input(Int32[n]) # => [1, 2, 3, 4, 5]# ```# ```# n, m = input(i, i64) # => {5, 10i64}# input(s, c[m]) # => {"foo", ['b', 'a', 'r']}# input(i[n]) # => [1, 2, 3, 4, 5]# ```## Input:# ```plain# 2 3# 1 2 3# 4 5 6# ```## ```# h, w = input(i, i) # => {2, 3}# input(i[h, w]) # => [[1, 2, 3], [4, 5, 6]]# ```# ```# input(i[i][i]) # => [[1, 2, 3], [4, 5, 6]]# ```## Input:# ```plain# 5 3# 3 1 4 2 5# 1 2# 2 3# 3 1# ```# ```# n, m = input(i, i) # => {5, 3}# input(i.pred[n]) # => [2, 0, 3, 1, 4]# input({i - 1, i - 1}[m]) # => [{0, 1}, {1, 2}, {2, 0}]# ```## Input:# ```plain# 3# 1 2# 2 2# 3 2# ```# ```# input({tmp = i, tmp == 1 ? i : i.pred}[i]) # => [{1, 2}, {2, 1}, {3, 1}]# ```class Scannerprivate def self.skip_to_not_spacepeek = STDIN.peeknot_space = peek.index { |x| x != 32 && x != 10 } || peek.sizeSTDIN.skip(not_space)enddef self.cskip_to_not_spaceSTDIN.read_char.not_nil!enddef self.sskip_to_not_spacepeek = STDIN.peekif index = peek.index { |x| x == 32 || x == 10 }STDIN.skip(index + 1)return String.new(peek[0, index])endString.build do |buffer|loop dobuffer.write peekSTDIN.skip(peek.size)peek = STDIN.peekbreak if peek.empty?if index = peek.index { |x| x == 32 || x == 10 }buffer.write peek[0, index]STDIN.skip(index)breakendendendendendmacro internal_input(s, else_ast){% if Scanner.class.has_method?(s.id) %}Scanner.{{s.id}}{% elsif s.stringify == "String" %}Scanner.s{% elsif s.stringify == "Char" %}Scanner.c{% elsif s.stringify =~ /[A-Z][a-z0-9_]*/ %}{{s.id}}.new(Scanner.s){% elsif String.has_method?("to_#{s}".id) %}Scanner.s.to_{{s.id}}{% else %}{{else_ast}}{% end %}endmacro internal_input_array(s, args){% for i in 0...args.size %}%size{i} = input({{args[i]}}){% end %}{% begin %}{% for i in 0...args.size %} Array.new(%size{i}) { {% end %}input({{s.id}}){% for i in 0...args.size %} } {% end %}{% end %}endmacro input(s){% if s.is_a?(Call) %}{% if s.receiver.is_a?(Nop) %}internal_input({{s.name}}, {{s.name}}({% for argument in s.args %} input({{argument}}), {% end %})){% elsif s.name.stringify == "[]" %}internal_input_array({{s.receiver}}, {{s.args}}){% else %}input({{s.receiver}}).{{s.name.id}}({% for argument in s.args %} input({{argument}}), {% end %}) {{s.block}}{% end %}{% elsif s.is_a?(TupleLiteral) %}{ {% for i in 0...s.size %} input({{s[i]}}), {% end %} }{% elsif s.is_a?(ArrayLiteral) %}[ {% for i in 0...s.size %} input({{s[i]}}), {% end %} ]{% elsif s.is_a?(RangeLiteral) %}Range.new(input({{s.begin}}), input({{s.end}}), {{s.excludes_end?}}){% elsif s.is_a?(If) %}{{s.cond}} ? input({{s.then}}) : input({{s.else}}){% elsif s.is_a?(Assign) %}{{s.target}} = input({{s.value}}){% else %}internal_input({{s.id}}, {{s.id}}){% end %}endmacro input(*s){ {% for s in s %} input({{s}}), {% end %} }end# require "atcoder/SCC"# ac-library.cr by hakatashi https://github.com/google/ac-library.cr## Copyright 2021 Google LLC## Licensed under the Apache License, Version 2.0 (the "License");# you may not use this file except in compliance with the License.# You may obtain a copy of the License at## https://www.apache.org/licenses/LICENSE-2.0## Unless required by applicable law or agreed to in writing, software# distributed under the License is distributed on an "AS IS" BASIS,# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.# See the License for the specific language governing permissions and# limitations under the License.module AtCoder# Implements [atcoder::scc_graph](https://atcoder.github.io/ac-library/master/document_en/scc.html).## ```# scc = AtCoder::SCC.new(3_i64)# scc.add_edge(0, 1)# scc.add_edge(1, 0)# scc.add_edge(2, 0)# scc.scc # => [Set{2}, Set{0, 1}]# ```class SCCalias Adjacency = NamedTuple(in: Array(Int64), out: Array(Int64))getter size : Int64getter adjacencies : Array(Adjacency)def initialize(@size)@adjacencies = Array(Adjacency).new(@size) { {in: [] of Int64, out: [] of Int64} }@topological_order = Array(Int64).new(@size)@visit_counts = Array(Int64).new(@size, 0_i64)@visited = Set(Int64).new@stack = Deque(Int64).new@groups = Array(Set(Int64)).newend# Implements atcoder::scc_graph.add_edge(from, to).def add_edge(from, to)@adjacencies[from][:out] << to.to_i64@adjacencies[to][:in] << from.to_i64endprivate def dfs(start)@stack << start@visited << startuntil @stack.empty?node = @stack.lastchildren = @adjacencies[node][:out]if @visit_counts[node] < children.sizechild = children[@visit_counts[node]]@visit_counts[node] += 1unless @visited.includes?(child)@visited << child@stack << childendelse@topological_order << node@stack.popendendendprivate def reverse_dfs(start)@stack << start@visited << startgroup = Set{start}until @stack.empty?node = @stack.popchildren = @adjacencies[node][:in]children.each do |child|unless @visited.includes?(child)@stack << child@visited << childgroup << childendendend@groups << groupend# Implements atcoder::scc_graph.scc().def scc@visited = Set(Int64).new@stack = Deque(Int64).new@visit_counts = Array(Int64).new(@size, 0_i64)@topological_order = Array(Int64).new(@size)@groups = Array(Set(Int64)).new@size.times do |node|unless @visited.includes?(node)dfs(node)endend@visited = Set(Int64).new@topological_order.reverse_each do |node|unless @visited.includes?(node)reverse_dfs(node)endend@groupsendendend# require "/graph/components"# require "../graph"# require "./graph/edge"struct WeightedEdge(T)include Comparable(WeightedEdge(T))property to : Int32, cost : Tdef initialize(@to, @cost : T)enddef <=>(other : WeightedEdge(T)){cost, to} <=> {other.cost, other.to}enddef to_s(io) : Nilio << '(' << to << ", " << cost << ')'enddef inspect(io) : Nilio << "->#{to}(#{cost})"endendstruct WeightedEdge2(T)include Comparable(WeightedEdge2(T))property from : Int32, to : Int32, cost : Tdef initialize(@from, @to, @cost : T)enddef initialize(@from, edge : WeightedEdge(T))@to, @cost = edge.to, edge.costenddef <=>(other : WeightedEdge2(T)){cost, from, to} <=> {other.cost, other.from, other.to}enddef reverseWeightedEdge2(T).new(to, from, cost)enddef sortWeightedEdge2(T).new(*{to, from}.minmax, cost)enddef to_s(io) : Nilio << '(' << from << ", " << to << ", " << cost << ')'enddef inspect(io) : Nilio << from << "->" << to << '(' << cost << ')'endendstruct UnweightedEdgeproperty to : Int32def initialize(@to)enddef cost1enddef to_s(io) : Nilio << toenddef inspect(io) : Nilio << "->" << toendendstruct UnweightedEdge2property from : Int32, to : Int32def initialize(@from, @to)enddef initialize(@from, edge : UnweightedEdge)@to = edge.toenddef cost1enddef reverseUnweightedEdge2.new(to, from)enddef sortUnweightedEdge2.new(*{to, from}.minmax)enddef to_s(io) : Nilio << '(' << from << ", " << to << ')'enddef inspect(io) : Nilio << from << "->" << toendendmodule Graph(Edge, Edge2)include Enumerable(Edge2)getter graph : Array(Array(Edge))def initialize(size : Int)@graph = Array(Array(Edge)).new(size) { [] of Edge }enddef initialize(size : Int, edges : Enumerable)initialize(size)add_edges(edges)end# Add *edge*.abstract def <<(edge : Edge2)# :ditto:def <<(edge : Tuple)self << Edge2.new(*edge)enddef add_edges(edges : Enumerable)edges.each { |edge| self << edge }enddelegate size, to: @graphdelegate :[], to: @graphdef each : Nil(0...size).each do |v|self[v].each do |edge|yield Edge2.new(v, edge)endendenddef reverseif self.class.directed?each_with_object(self.class.new(size)) do |edge, reversed|reversed << edge.reverseendelsedupendenddef to_undirectedif self.class.directed?each_with_object(self.class.new(size)) do |edge, graph|graph << edgegraph << edge.reverse if self.class.directed?endelsedupendendendclass DirectedGraph(T)include Graph(WeightedEdge(T), WeightedEdge2(T))def initialize(size : Int)superenddef initialize(size : Int, edges : Enumerable(WeightedEdge2(T)))superenddef initialize(size : Int, edges : Enumerable({Int32, Int32, T}))superenddef <<(edge : WeightedEdge2(T))raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size@graph[edge.from] << WeightedEdge.new(edge.to, edge.cost)selfenddef self.weighted?trueenddef self.directed?trueendendclass UndirectedGraph(T)include Graph(WeightedEdge(T), WeightedEdge2(T))def initialize(size : Int)superenddef initialize(size : Int, edges : Enumerable(WeightedEdge2(T)))superenddef initialize(size : Int, edges : Enumerable({Int32, Int32, T}))superenddef <<(edge : WeightedEdge2(T))raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size@graph[edge.from] << WeightedEdge.new(edge.to, edge.cost)@graph[edge.to] << WeightedEdge.new(edge.from, edge.cost)selfenddef self.weighted?trueenddef self.directed?falseendendclass UnweightedDirectedGraphinclude Graph(UnweightedEdge, UnweightedEdge2)def initialize(size : Int)superenddef initialize(size : Int, edges : Enumerable)superenddef <<(edge : UnweightedEdge2)raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size@graph[edge.from] << UnweightedEdge.new(edge.to)selfenddef self.weighted?falseenddef self.directed?trueendendclass UnweightedUndirectedGraphinclude Graph(UnweightedEdge, UnweightedEdge2)def initialize(size : Int)superenddef initialize(size : Int, edges : Enumerable)superenddef <<(edge : UnweightedEdge2)raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size@graph[edge.from] << UnweightedEdge.new(edge.to)@graph[edge.to] << UnweightedEdge.new(edge.from)selfenddef 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 }enddef self.weighted?falseenddef self.directed?falseendendmodule Graph(Edge, Edge2)# Returns `{components size, index, groups}`.def componentsundirected = to_undirectedindex = Array(Int32?).new(size, nil)groups = [] of Set(Int32)id = 0size.times do |v|next if index[v]que = Deque{v}groups << Set(Int32).newwhile u = que.shift?next if index[u]index[u] = idgroups[id] << uundirected[u].each do |edge|que << edge.to if index[edge.to].nil?endendid += 1end{id, index.map(&.not_nil!), groups}endend# require "/datastructure/union_find"class UnionFind@d : Array(Int32)def initialize(n : Int)@d = Array.new(n, -1)enddef initialize(n : Int, edges : Enumerable({Int32, Int32}))initialize(n)edges.each { |u, v| unite(u, v) }enddef root(x : Int)@d[x] < 0 ? x : (@d[x] = root(@d[x]))enddef unite(x : Int, y : Int)x = root(x)y = root(y)return false if x == yx, y = y, x if @d[x] > @d[y]@d[x] += @d[y]@d[y] = xtrueenddef same?(x : Int, y : Int)root(x) == root(y)enddef size(x : Int)-@d[root(x)]enddef groupsgroups = Hash(Int32, Set(Int32)).new { |h, k| h[k] = Set(Int32).new }@d.size.times do |i|groups[root(i)] << iendgroups.values.to_setendendn, m = input(i, i)edges = input({i - 1, i - 1}[m])graph = UnweightedDirectedGraph.new n, edgesscc = AtCoder::SCC.new(n.to_i64)graph.each do |edge|scc.add_edge edge.from, edge.toendscc_groups = scc.scc.map &.map(&.to_i)scc_id = [-1] * nscc_groups.each_with_index do |group, id|group.each { |i| scc_id[i] = id }endk, id, groups = graph.componentsans = [] of {Int32, Int32}has_cycle = [false] * kscc_groups.each do |group|v = group.firsthas_cycle[id[v]] = true if group.size > 1endtopo = Array.new(k) { [] of Int32 }scc_groups.each do |group|group.each do |v|topo[id[v]] << vendend(0...k).each do |i|group = groups[i].to_aif has_cycle[i](0...group.size).each do |i|ans << {group[i], group[i.succ % group.size]}endelsetopo[i].each_cons_pair do |u, v|ans << {u, v}endendendputs ans.size, ans.join('\n', &.join(' ', &.succ))