Submission #42277952

---

Source Code Expand

END { load __FILE__ unless $stdin.eof? }

class PairingHeap
  class Node
    attr_reader :key, :children

    def initialize(key)
      @key = key
      @children = []
    end
  end

  def initialize(pushes = [])
    @heaps = pushes.map { |key| Node.new(key) }
  end

  def push(key)
    @heaps << Node.new(key)
    return self
  end

  def shift
    return nil if @heaps.empty?

    reshape
    key, @heaps = @heaps[0].key, @heaps[0].children
    return key
  end

  def first
    return nil if @heaps.empty?

    reshape
    return @heaps[0].key
  end

  private

  def reshape
    @heaps.sort_by!(&:key)
    @heaps.size.pred.times do
      h = @heaps.pop
      @heaps[-1].children << h
    end
  end
end

module HeapWithObject
  def initialize(pushes = [])
    @objs = pushes.group_by(&:first)
        .transform_values! { |q| q.map!(&:last) }
    super(@objs.keys)
  end

  def push(key, obj)
    if (q = @objs[key])
      q << obj
      return self
    end

    @objs[key] = [obj]
    return super(key)
  end

  def shift
    key = first
    return unless key

    q = @objs[key]
    obj = q.shift

    if q.empty?
      @objs.delete(key)
      super  # == key
    end

    return key, obj
  end

  def first_pair
    key = first
    return unless key
    return key, @objs[key][0]
  end
end

class PriorityQueue < PairingHeap
  prepend HeapWithObject
end

n, m, k = gets.split.map!(&:to_i)

@nbrs = Array.new(n + 1) { [] }
m.times do
  a, b = gets.split.map!(&:to_i)
  @nbrs[a] << b
  @nbrs[b] << a
end

@guards = Array.new(n + 1, -1)
pushes = k.times.map do
  g, h = gets.split.map!(&:to_i)
  @guards[g] = h
  [-h, g]
end
pq = PriorityQueue.new(pushes)

while (h, v = pq.shift)
  h = -h
  next if h < @guards[v]

  h -= 1
  @nbrs[v].each do |u|
    next if @guards[u] >= h
    @guards[u] = h
    pq.push(-h, u)
  end
end

idx = (1..n).select { |v| @guards[v] >= 0 }
puts idx.size
puts idx * ' '

__END__

Submission Info

Judge Result