#680019 (Crystal) No.1370 置換門松列

• 問題: No.1370 置換門松列
• ユーザー: yuruhiya
• 提出日時: 2021-07-21 21:16:59
• 言語: Crystal (1.11.2)
• 結果: AC
• 実行時間: 40 ms / 2,000 ms
• コード長: 6,452 bytes
• コンパイル時間: 14,141 ms
• コンパイル使用メモリ: 296,248 KB
• 実行使用メモリ: 11,904 KB
• 最終ジャッジ日時: 2024-09-14 19:27:37
• 合計ジャッジ時間: 16,010 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	2 ms; 6,812 KB
testcase_02	AC	1 ms; 6,944 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	2 ms; 6,940 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	2 ms; 6,944 KB
testcase_08	AC	2 ms; 6,940 KB
testcase_09	AC	2 ms; 6,940 KB
testcase_10	AC	2 ms; 6,940 KB
testcase_11	AC	2 ms; 6,940 KB
testcase_12	AC	2 ms; 6,944 KB
testcase_13	AC	2 ms; 6,944 KB
testcase_14	AC	2 ms; 6,940 KB
testcase_15	AC	2 ms; 6,940 KB
testcase_16	AC	2 ms; 6,940 KB
testcase_17	AC	2 ms; 6,944 KB
testcase_18	AC	2 ms; 6,940 KB
testcase_19	AC	2 ms; 6,944 KB
testcase_20	AC	2 ms; 6,940 KB
testcase_21	AC	35 ms; 11,776 KB
testcase_22	AC	28 ms; 11,776 KB
testcase_23	AC	32 ms; 11,776 KB
testcase_24	AC	20 ms; 7,936 KB
testcase_25	AC	40 ms; 11,904 KB
testcase_26	AC	40 ms; 11,904 KB
testcase_27	AC	29 ms; 10,496 KB
testcase_28	AC	29 ms; 10,496 KB
testcase_29	AC	23 ms; 10,496 KB

ソースコード

# require "/graph/topological_sort"
# require "../graph"
# require "./graph/edge"
struct WeightedEdge(T)
  include Comparable(WeightedEdge(T))

  property to : Int32, cost : T

  def initialize(@to, @cost : T)
  end

  def <=>(other : WeightedEdge(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 WeightedEdge2(T)
  include Comparable(WeightedEdge2(T))

  property from : Int32, to : Int32, cost : T

  def initialize(@from, @to, @cost : T)
  end

  def initialize(@from, edge : WeightedEdge(T))
    @to, @cost = edge.to, edge.cost
  end

  def <=>(other : WeightedEdge2(T))
    {cost, from, to} <=> {other.cost, other.from, other.to}
  end

  def reverse
    WeightedEdge2(T).new(to, from, cost)
  end

  def sort
    WeightedEdge2(T).new(*{to, from}.minmax, cost)
  end

  def to_s(io) : Nil
    io << '(' << from << ", " << to << ", " << cost << ')'
  end

  def inspect(io) : Nil
    io << from << "->" << to << '(' << cost << ')'
  end
end

struct UnweightedEdge
  property to : Int32

  def initialize(@to)
  end

  def cost
    1
  end

  def to_s(io) : Nil
    io << to
  end

  def inspect(io) : Nil
    io << "->" << to
  end
end

struct UnweightedEdge2
  property from : Int32, to : Int32

  def initialize(@from, @to)
  end

  def initialize(@from, edge : UnweightedEdge)
    @to = edge.to
  end

  def cost
    1
  end

  def reverse
    UnweightedEdge2.new(to, from)
  end

  def sort
    UnweightedEdge2.new(*{to, from}.minmax)
  end

  def to_s(io) : Nil
    io << '(' << from << ", " << to << ')'
  end

  def inspect(io) : Nil
    io << from << "->" << to
  end
end

module Graph(Edge, Edge2)
  include Enumerable(Edge2)

  getter graph : Array(Array(Edge))

  def initialize(size : Int)
    @graph = Array(Array(Edge)).new(size) { [] of Edge }
  end

  def 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)
  end

  def add_edges(edges : Enumerable)
    edges.each { |edge| self << edge }
  end

  delegate size, to: @graph
  delegate :[], to: @graph

  def each : Nil
    (0...size).each do |v|
      self[v].each do |edge|
        yield Edge2.new(v, edge)
      end
    end
  end

  def reverse
    if self.class.directed?
      each_with_object(self.class.new(size)) do |edge, reversed|
        reversed << edge.reverse
      end
    else
      dup
    end
  end

  def to_undirected
    if self.class.directed?
      each_with_object(self.class.new(size)) do |edge, graph|
        graph << edge
        graph << edge.reverse if self.class.directed?
      end
    else
      dup
    end
  end
end

class DirectedGraph(T)
  include Graph(WeightedEdge(T), WeightedEdge2(T))

  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Enumerable(WeightedEdge2(T)))
    super
  end

  def initialize(size : Int, edges : Enumerable({Int32, Int32, T}))
    super
  end

  def <<(edge : WeightedEdge2(T))
    raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size
    @graph[edge.from] << WeightedEdge.new(edge.to, edge.cost)
    self
  end

  def self.weighted?
    true
  end

  def self.directed?
    true
  end
end

class UndirectedGraph(T)
  include Graph(WeightedEdge(T), WeightedEdge2(T))

  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Enumerable(WeightedEdge2(T)))
    super
  end

  def initialize(size : Int, edges : Enumerable({Int32, Int32, T}))
    super
  end

  def <<(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)
    self
  end

  def self.weighted?
    true
  end

  def self.directed?
    false
  end
end

class UnweightedDirectedGraph
  include Graph(UnweightedEdge, UnweightedEdge2)

  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Enumerable)
    super
  end

  def <<(edge : UnweightedEdge2)
    raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size
    @graph[edge.from] << UnweightedEdge.new(edge.to)
    self
  end

  def self.weighted?
    false
  end

  def self.directed?
    true
  end
end

class UnweightedUndirectedGraph
  include Graph(UnweightedEdge, UnweightedEdge2)

  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Enumerable)
    super
  end

  def <<(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)
    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

  def self.weighted?
    false
  end

  def self.directed?
    false
  end
end

# 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] += 1
    end
  end

  # Returns table of outdegree.
  def outdegree : Array(Int32)
    each_with_object(Array.new(size, 0)) do |edge, cnt|
      cnt[edge.from] += 1
    end
  end
end

module Graph(Edge, Edge2)
  def topological_sort : Array(Int32)?
    deg = indegree
    que = Deque(Int32).new
    size.times { |i| que << i if deg[i] == 0 }
    result = Array(Int32).new(size)
    while v = que.shift?
      result << v
      self[v].each do |edge|
        que << edge.to if (deg[edge.to] -= 1) == 0
      end
    end
    deg.any? { |x| x > 0 } ? nil : result
  end
end

n, m = read_line.split.map(&.to_i)
a = read_line.split.map(&.to_i.pred)
if a.each_cons(3).any? { |(x, y, z)| x == y || x == z || y == z }
  puts "No"
else
  graph = UnweightedDirectedGraph.new(m)
  (0...n - 1).each do |i|
    if i.even?
      graph << {a[i], a[i + 1]}
    else
      graph << {a[i + 1], a[i]}
    end
  end
  if order = graph.topological_sort
    ans = [-1] * m
    order.each_with_index { |x, i| ans[x] = i }
    puts "Yes", ans.join(' ', &.succ)
  else
    puts "No"
  end
end