結果
問題 | No.1640 簡単な色塗り |
ユーザー |
![]() |
提出日時 | 2021-08-07 13:10:15 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 172 ms / 2,000 ms |
コード長 | 18,075 bytes |
コンパイル時間 | 10,970 ms |
コンパイル使用メモリ | 304,128 KB |
実行使用メモリ | 57,264 KB |
最終ジャッジ日時 | 2024-06-29 16:48:36 |
合計ジャッジ時間 | 21,780 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
# require "/template"# 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}]# ```## Input:# ```plain# 3# 1 2# 2 3# 3 1# ```# ```# n = input(i)# input_column({Int32, Int32}, n) # => {[1, 2, 3], [2, 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(type, else_ast){% if Scanner.class.has_method?(type.id) %}Scanner.{{type.id}}{% elsif type.stringify == "String" %}Scanner.s{% elsif type.stringify == "Char" %}Scanner.c{% elsif type.stringify =~ /[A-Z][a-z0-9_]*/ %}{{type.id}}.new(Scanner.s){% elsif String.has_method?("to_#{type}".id) %}Scanner.s.to_{{type.id}}{% else %}{{else_ast}}{% end %}endmacro internal_input_array(type, 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({{type.id}}){% for i in 0...args.size %} } {% end %}{% end %}endmacro input(type){% if type.is_a?(Call) %}{% if type.receiver.is_a?(Nop) %}internal_input({{type.name}}, {{type.name}}({% for argument in type.args %} input({{argument}}), {% end %})){% elsif type.name.stringify == "[]" %}internal_input_array({{type.receiver}}, {{type.args}}){% else %}input({{type.receiver}}).{{type.name.id}}({% for argument in type.args %} input({{argument}}), {% end %}) {{type.block}}{% end %}{% elsif type.is_a?(TupleLiteral) %}{ {% for i in 0...type.size %} input({{type[i]}}), {% end %} }{% elsif type.is_a?(ArrayLiteral) %}[ {% for i in 0...type.size %} input({{type[i]}}), {% end %} ]{% elsif type.is_a?(RangeLiteral) %}Range.new(input({{type.begin}}), input({{type.end}}), {{type.excludes_end?}}){% elsif type.is_a?(If) %}{{type.cond}} ? input({{type.then}}) : input({{type.else}}){% elsif type.is_a?(Assign) %}{{type.target}} = input({{type.value}}){% else %}internal_input({{type.id}}, {{type.id}}){% end %}endmacro input(*types){ {% for type in types %} input({{type}}), {% end %} }endmacro input_column(types, size){% for type, i in types %}%array{i} = Array({{type}}).new({{size}}){% end %}{{size}}.times do{% for type, i in types %}%array{i} << input({{type}}){% end %}end{ {% for type, i in types %} %array{i}, {% end %} }end# require "./tuple/times"struct Tupledef times(&block) : Nil{% begin %}{% for i in 0...@type.size %}{% if @type[i].has_method?(:each) %}self[{{i}}].each do |i{{i}}|{% else %}self[{{i}}].times do |i{{i}}|{% end %}{% end %}yield({% for i in 0...@type.size %} i{{i}}, {% end %}){% for i in 0...@type.size %} end {% end %}{% end %}endprivate class TimesIterator(T)include Iterator(T)def initialize(@n : T)tuple = {% begin %}{ {% for i in 0...T.size %} T[{{i}}].zero, {% end %} }{% end %}@index = tuple.as(T)@first = trueenddef nextif @first@first = falsereturn @indexend{% begin %}{%type = @type.type_vars[0]size = type.size%}{% for i in 1..size %}if @index[{{size - i}}] < @n[{{size - i}}] - 1@index = {{% for j in 0...size %}{% if j < size - i %}@index[{{j}}],{% elsif j == size - i %}@index[{{j}}] + 1,{% else %}{{type[j]}}.zero,{% end %}{% end %}}return @indexend{% end %}stop{% end %}endenddef timesTimesIterator(self).new(self)endend# require "./comparable/min_max"module Comparable(T)def min(x : T)self > x ? x : selfenddef max(x : T)self < x ? x : selfendend# require "./array/new"class Arraydef self.new(sizes : Tuple(*T), initial_value) forall T{% begin %}{% for i in 0...T.size %} Array.new(sizes[{{i}}]) { {% end %}initial_value{% for i in 0...T.size %} } {% end %}{% end %}enddef self.new(sizes : Tuple(*T), &block) forall T{% begin %}{% for i in 0...T.size %} Array.new(sizes[{{i}}]) { |%i{i}| {% end %}yield({% for i in 0...T.size %} %i{i}, {% end %}){% for i in 0...T.size %} } {% end %}{% end %}endend# require "./array/change"class Array(T)def chmin(i : Int, value : T)(self[i] > value).tap do |f|self[i] = value if fendendprotected def chmin(i : Int, *indexes, value)self[i].chmin(*indexes, value: value)enddef chmin(indexes : Tuple, value)chmin(*indexes, value: value)enddef chmax(i : Int, value : T)(self[i] < value).tap do |f|self[i] = value if fendendprotected def chmax(i : Int, *indexes, value)self[i].chmax(*indexes, value: value)enddef chmax(indexes : Tuple, value)chmax(*indexes, value: value)endend# require "/graph/decompose"# 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 initialize(@to, cost)enddef cost1enddef to_s(io) : Nilio << toenddef inspect(io) : Nilio << "->" << toendendstruct UnweightedEdge2property from : Int32, to : Int32def initialize(@from, @to)enddef initialize(@from, @to, cost)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: @graph# Yields each edge of the graph, ans returns `nil`.def 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?endelsedupendenddef to_s(io : IO) : Nilio << '['join(", ", io) do |edge, io|edge.inspect ioendio << ']'enddef inspect(io : IO) : Nilio << "[\n"graph.each do |edges|io << " " << edges << ",\n"endio << ']'endendclass 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?falseendend# 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_setendendmodule Graph(Edge, Edge2)# Decomposes the graph into each conected components.def decompose : {Array(self), Array({Int32, Int32}), Array(Array(Int32))}uf = UnionFind.new(size)each do |edge|uf.unite(edge.from, edge.to)endgroups = uf.groups.to_aindex = Array.new(size, {-1, -1})groups.each_with_index do |group, i|group.each_with_index do |v, j|index[v] = {i, j}endendnormalize = Array.new(groups.size) { |i| Array.new(groups[i].size, -1) }index.each_with_index { |(i, j), k| normalize[i][j] = k }graphs = Array.new(groups.size) { |i| self.class.new(groups[i].size) }if self.class.directed?each do |edge|i1, j1 = index[edge.from]_, j2 = index[edge.to]graphs[i1] << {j1, j2, edge.cost}endelseedge_set = Set(Edge2).neweach do |edge|if edge_set.add?(edge.sort)i1, j1 = index[edge.from]_, j2 = index[edge.to]graphs[i1] << {j1, j2, edge.cost}endendend{graphs, index, normalize}endend# require "/graph/namori_decompose"# require "../graph"# require "./degree"# require "../graph"module Graph(Edge, Edge2)# Returns table of indegree.def indegree : Array(Int32)each_with_object(Array.new(size, 0)) do |edge, cnt|cnt[edge.to] += 1endend# Returns table of outdegree.def outdegree : Array(Int32)each_with_object(Array.new(size, 0)) do |edge, cnt|cnt[edge.from] += 1endendendmodule Graph(Edge, Edge2)# Returns forest and cycle of the undirected graph with equal number of vertices and edges.def namori_decompose : {self, Array(Int32)}raise ArgumentError.new unless !self.class.directed?raise ArgumentError.new unless size == graph.sum(&.size) // 2deg = Array.new(size) { |i| self[i].size }que = Deque(Int32).newflag = Array.new(size, false)(0...size).each do |i|if deg[i] == 1que << iflag[i] = trueendendforest = self.class.new(size)while v = que.shift?self[v].each do |edge|next if flag[edge.to]deg[edge.to] -= 1forest << Edge2.new(v, edge)if deg[edge.to] == 1que << edge.toflag[edge.to] = trueendendendcycle = [] of Int32(0...size).each do |i|que << i unless flag[i]while v = que.pop?next if flag[v]cycle << vflag[v] = trueself[v].each do |edge|que << edge.to unless flag[edge.to]endendend{forest, cycle}endenddef dfs(graph, v, p, dist, a)a[v] = distgraph[v].each do |edge|next if edge.to == pdfs(graph, edge.to, v, dist + 1, a)endendn = input(i)edges = input({i - 1, i - 1}[n])ans = Array(Int32?).new(n, nil)g = UndirectedGraph.new n, edges.each_with_index.map { |(e, i)| {e[0], e[1], i} }graphs, index, normalize = g.decomposegraphs.zip(normalize) do |graph, normalize|if graph.size != graph.graph.sum(&.size) // 2puts "No"; exitendforest, cycle = graph.namori_decomposedist = [0] * graph.sizecycle_index = [nil.as Int32?] * graph.sizecycle.each_with_index do |v, i|cycle_index[v] = idfs(forest, v, -1, 0, dist)endflag = falsegraph.each do |edge|d_from, d_to = dist[edge.from], dist[edge.to]c_from, c_to = cycle_index[edge.from], cycle_index[edge.to]if d_from < d_toans[edge.cost] = normalize[edge.to]elsif d_from == d_to && c_from.not_nil! <= c_to.not_nil!if {edge.from, edge.to} == {cycle.first, cycle.last}if cycle.size == 2ans[edge.cost] = normalize[flag ? edge.to : edge.from]flag = trueelseans[edge.cost] = normalize[edge.to]endelseans[edge.cost] = normalize[edge.from]endendendendputs "Yes", ans.join('\n', &.not_nil!.succ)