#2428923

Solution for ALDS1_7_A: Rooted Trees by hiroyuking

Source Code Status Test Cases
    Policy: public     Reviewed: 30    
00.51 sec    26204 KB    63 lines     1165 bytes    2017-07-13 14:58
lines = $stdin.read
array = lines.split("\n")

N = array[0].to_i
Node = Struct.new(:parent, :left, :right)

nodes = Array.new(N) { Node.new }

def get_depth(id, nodes)
  d = 0
  while ! nodes[id].parent.nil? do
    id = nodes[id].parent
    d += 1
  end
  d
end

def get_children(id, nodes)
  children = []
  c = nodes[id].left
  while not c.nil?
    children << c
    c = nodes[c].right
  end
  children
end

for i in 1...(array.size)

  carray = array[i].split(" ")
  id = carray[0].to_i
  k  = carray[1].to_i
  c  = carray.slice(2, carray.length+1).map(&:to_i)

  # set parents for each children
  c.each do |child|
    nodes[child].parent = id
  end

  # set left node for this node
  nodes[id].left = c.first

  # set left/right nodes
  c.inject do |l, r|
    nodes[l].right = r
  end
end

nodes.each_with_index do |node, index|

  children = get_children(index, nodes)

  type = if node.parent.nil?
           "root"
         elsif children.empty?
           "leaf"
         else
           "internal node"
         end

  puts "node #{index}: parent = #{node.parent.nil? ? -1 : node.parent}, depth = #{get_depth(index, nodes)}, #{type}, #{children.to_s}"
end

Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 8/8 Ruby CPU: 00.51 sec Memory: 26204 KB Length: 1165 B 2017-07-13 14:58 2017-07-13 14:58
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.04 sec 8616 KB
Case #2: : Accepted 00.03 sec 8552 KB
Case #3: : Accepted 00.03 sec 8736 KB
Case #4: : Accepted 00.03 sec 8648 KB
Case #5: : Accepted 00.02 sec 8616 KB
Case #6: : Accepted 00.02 sec 8584 KB
Case #7: : Accepted 00.50 sec 25932 KB
Case #8: : Accepted 00.51 sec 26204 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags