Submission #287390


Source Code Expand

Copy
num, pos = gets.chomp.split(" ")
pos      = pos.to_i
dia      = gets.chomp.split(" ")
num_d    = dia.count("1")
edge = Array.new
while line = gets
  a, b = line.split(" ")
  edge.push( [ a.to_i-1, b.to_i-1 ] )
end
arr = Array.new
dia.each_with_index{|e,i|
  arr[i] = Hash.new
  arr[i]["d"] = ( e == "1" )
}
edge.each{|a,b|
  if arr[a]["children"] == nil
    arr[a]["children"] = [ b ]
  else
    arr[a]["children"].push(b)
  end

  if arr[b]["parent"] == nil
    arr[b]["parent"] = a
  end
}

begin
  cut = 0
  arr.each_with_index{|n,i|
    if n["children"] == nil && n["d"] == false
      arr[i] = nil
      arr.each_with_index{|nn,ii|
        next if nn == nil
        if nn["children"] != nil && nn["children"].include?(i)
          nn["children"].delete(i)
          if nn["children"] == []
            nn.delete("children")
          end
        end
      }
      cut += 0
    end
  }
end while cut > 0

root = nil
arr.each_with_index{|e,i|
  next if e == nil
  root = i if e["parent"] == nil
}

@cost  = 0
@first = nil
@last  = nil

def search( arr, num )
  return if arr[num] == nil
  if arr[num]["d"]
    @first = @cost if @first == nil
    @last  = @cost
  end
  return if arr[num]["children"] == nil
  arr[num]["children"].each{|e|
    @cost += 1
    search( arr, e )
  }
end
search( arr, root )
# p [ @first, @last, @cost ] 
puts 2 * ( @last - @first )

Submission Info

Submission Time
Task B - ツリーグラフ
User yosidaa
Language Ruby (1.9.3)
Score 0
Code Size 1432 Byte
Status WA
Exec Time 64 ms
Memory 4384 KB

Compile Error

./Main.rb:15: warning: shadowing outer local variable - a
./Main.rb:15: warning: shadowing outer local variable - b

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 6
WA × 13
RE × 1
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_line01.txt, subtask1_line02.txt, subtask1_line03.txt, subtask1_line04.txt, subtask1_line05.txt, subtask1_line06.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_random06.txt, subtask1_random07.txt, subtask1_random08.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 57 ms 4208 KB
subtask0_sample_02.txt AC 57 ms 4204 KB
subtask1_line01.txt AC 58 ms 4212 KB
subtask1_line02.txt WA 58 ms 4340 KB
subtask1_line03.txt WA 61 ms 4288 KB
subtask1_line04.txt WA 58 ms 4340 KB
subtask1_line05.txt AC 57 ms 4384 KB
subtask1_line06.txt RE 57 ms 4380 KB
subtask1_random01.txt WA 60 ms 4208 KB
subtask1_random02.txt WA 56 ms 4208 KB
subtask1_random03.txt WA 60 ms 4208 KB
subtask1_random04.txt WA 61 ms 4196 KB
subtask1_random05.txt WA 63 ms 4212 KB
subtask1_random06.txt WA 62 ms 4212 KB
subtask1_random07.txt WA 64 ms 4216 KB
subtask1_random08.txt WA 58 ms 4208 KB
subtask1_special01.txt AC 56 ms 4208 KB
subtask1_special02.txt WA 60 ms 4208 KB
subtask1_special03.txt AC 57 ms 4208 KB
subtask1_special04.txt WA 60 ms 4212 KB