Submission #1676182


Source Code Expand

lines = $stdin.read
array = lines.split("\n")

# Queue
class Array
  alias_method :enqueue, :push
  alias_method :dequeue, :shift
end

#
# u : Index of nodes starting from 1...N
# k : degree of this node
# v : array of vertices connected with this node
# c : :white(=undiscovered), :gray(=frontier), :black(finished searching)
# d : distance when the vertex is first discovered
# pi: predecessor vertex
Node = Struct.new(:u, :k, :v, :c, :d, :pi)

class Graph

  attr :nodes, true

  def initialize(n)
    @nodes = Array.new(n){ Node.new }
  end

  def add_graph_node(u, v)
    @nodes[u-1].u = u
    (@nodes[u-1].v ||= []).push(v)
    @nodes[u-1].k = @nodes[u-1].v.length
    @nodes[u-1].c = :white
    @nodes[u-1].d = -1
    @nodes[u-1].pi = nil
  end

  def reset()
    @nodes.each do |node|
      node.c  = :white
      node.d  = -1
      node.pi = nil
    end
  end

  def dist()
    puts "d : #{@nodes.map{|node| node.d}.to_a.to_s}"
    puts "pi: #{@nodes.map{|node| node.pi}.to_a.to_s}"
  end

  def bfs(start, queue)

    start_idx = (start - 1).to_i
    @nodes[start_idx].c  = :gray
    @nodes[start_idx].d  = 0
    @nodes[start_idx].pi = nil
    queue.enqueue(@nodes[start_idx])

    while not queue.empty?

      u = queue.dequeue
      break if u.v.nil?

      u.v.each do |label|
        v = @nodes[label-1]
        if v.c == :white
          v.c  = :gray
          v.d  = u.d.to_i + 1
          v.pi = u
          queue.enqueue(v)
        end
      end
      u.c = :black
    end
  end
end

# start
#lines = $stdin.read
array = lines.split("\n")

N     = array[0].to_i
Q     = array[N].to_i
graph = Graph.new(N)

for i in 1...N
  seps = array[i].split(" ")
  u,v  = seps.map(&:to_i) # .map{|n| n-1}
  #puts "add_graph_node(#{u} <--> #{v})"
  graph.add_graph_node(u, v)
  graph.add_graph_node(v, u)
end

# graph.nodes.each do |node|
#     puts node.to_s
# end

for j in N+1...N+Q+1
  src,dst = array[j].split(" ").map(&:to_i)
  # puts "#{src} to #{dst}"
  graph.reset()
  graph.bfs(src, [])
  #puts graph.dist
  puts graph.nodes[dst.to_i-1].d.to_i + 1
end

Submission Info

Submission Time
Task D - 閉路
User hiroyuking
Language Ruby (2.3.3)
Score 30
Code Size 2168 Byte
Status TLE
Exec Time 2112 ms
Memory 58604 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 0 / 70
Status
AC × 3
AC × 12
AC × 16
TLE × 11
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 8 ms 1788 KB
subtask0_sample02.txt AC 8 ms 1788 KB
subtask0_sample03.txt AC 8 ms 1788 KB
subtask1_01.txt AC 446 ms 33788 KB
subtask1_02.txt AC 442 ms 33788 KB
subtask1_03.txt AC 8 ms 1788 KB
subtask1_04.txt AC 8 ms 1788 KB
subtask1_05.txt AC 13 ms 2044 KB
subtask1_06.txt AC 12 ms 2044 KB
subtask1_07.txt AC 522 ms 36092 KB
subtask1_08.txt AC 517 ms 35452 KB
subtask1_09.txt AC 531 ms 35196 KB
subtask1_10.txt AC 531 ms 35068 KB
subtask1_11.txt AC 509 ms 35068 KB
subtask1_12.txt AC 517 ms 35068 KB
subtask2_01.txt TLE 2112 ms 54524 KB
subtask2_02.txt TLE 2112 ms 54524 KB
subtask2_03.txt AC 1234 ms 18412 KB
subtask2_04.txt TLE 2109 ms 17660 KB
subtask2_05.txt TLE 2109 ms 16508 KB
subtask2_06.txt TLE 2109 ms 14204 KB
subtask2_07.txt TLE 2112 ms 57164 KB
subtask2_08.txt TLE 2112 ms 58604 KB
subtask2_09.txt TLE 2112 ms 56188 KB
subtask2_10.txt TLE 2112 ms 56188 KB
subtask2_11.txt TLE 2112 ms 56060 KB
subtask2_12.txt TLE 2111 ms 58260 KB