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 |
|
|
|
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 |