gmo61520

Untitled

Mar 19th, 2016
222
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.47 KB | None | 0 0
  1. # coding: utf-8
  2. import sys
  3. from queue import *
  4.  
  5. # строим граф из входных данных
  6. def solve_graph(input_list):
  7. vertices_number = input_list[0][0]
  8. root_id = input_list[0][1]
  9. edges_number = vertices_number - 1
  10.  
  11. vertices = []
  12. for i in range(0, vertices_number):
  13. vertices.append({ 'id': i, 'left': None, 'right': None })
  14.  
  15. root_vertice = vertices[root_id]
  16.  
  17. # создаём таблицу «ID вершины → список соседей»
  18. # для больших деревьев с ней где-то в ≈310 раз быстрее
  19. edges = {}
  20. for i in range(1, edges_number + 1):
  21. entry = input_list[i]
  22.  
  23. if entry[0] in edges:
  24. edges[entry[0]].append(entry[1])
  25. else:
  26. edges[entry[0]] = [ entry[1] ]
  27.  
  28. if entry[1] in edges:
  29. edges[entry[1]].append(entry[0])
  30. else:
  31. edges[entry[1]] = [ entry[0] ]
  32.  
  33. arrange_children_wrapper = None
  34.  
  35. # распихаем потомков по слотам
  36. def arrange_children(vertice, vertice_parent_id):
  37. vertice_id = vertice['id']
  38.  
  39. # добавляем потомка в незанятый слот
  40. def add_child(child):
  41. if vertice['left'] == None:
  42. vertice['left'] = child
  43. else:
  44. vertice['right'] = child
  45.  
  46. # быстренько выдёргиваем соседей из той таблицы
  47. if vertice_id in edges:
  48. for i in edges[vertice_id]:
  49. if i != vertice_parent_id:
  50. add_child(vertices[i])
  51.  
  52. # без рекурсии
  53. queue = Queue()
  54.  
  55. current_vertice = root_vertice
  56. current_parent_id = -1
  57.  
  58. while True:
  59. arrange_children(current_vertice, current_parent_id)
  60.  
  61. left = current_vertice['left']
  62. right = current_vertice['right']
  63. current_parent_id = current_vertice['id']
  64.  
  65. if left != None:
  66. current_vertice = left
  67. if right != None:
  68. queue.put(( right, current_parent_id ))
  69. elif right != None:
  70. current_vertice = right
  71. elif not queue.empty():
  72. current_vertice, current_parent_id = queue.get()
  73. else:
  74. break
  75.  
  76. return root_vertice
  77.  
  78. # размер графа (пусть и пострашнее, зато теперь без рекурсии)
  79. def calculate_width(vertice):
  80. if vertice == None: return 0
  81.  
  82. queue = Queue()
  83. current_vertice = vertice
  84.  
  85. width = 0
  86.  
  87. while True:
  88. width = width + 1
  89.  
  90. left = current_vertice['left']
  91. right = current_vertice['right']
  92.  
  93. if left != None:
  94. current_vertice = left
  95. if right != None:
  96. queue.put(right)
  97. elif right != None:
  98. current_vertice = right
  99. elif not queue.empty():
  100. current_vertice = queue.get()
  101. else:
  102. return width
  103.  
  104. def calculate_height(vertice):
  105. if vertice == None: return 0
  106.  
  107. queue = Queue()
  108. current_vertice = vertice
  109. current_height = 0
  110.  
  111. height = 0
  112.  
  113. while True:
  114. current_height = current_height + 1
  115. height = max(height, current_height)
  116.  
  117. left = current_vertice['left']
  118. right = current_vertice['right']
  119.  
  120. if left != None:
  121. current_vertice = left
  122.  
  123. if right != None:
  124. queue.put(( right, current_height ))
  125. elif right != None:
  126. current_vertice = right
  127. elif not queue.empty():
  128. current_vertice, current_height = queue.get()
  129. else:
  130. return height
  131.  
  132. # рекурсивный расчёт координат вершин
  133. def calculate_positions(vertice, offset_x = 0, offset_y = -1):
  134. if vertice == None: return
  135.  
  136. # зачем-то ось Y направлена вверх, «против» графа, так что начнём отсчёт с
  137. # высоты и пойдём наверх
  138. if offset_y == -1: offset_y = calculate_height(vertice) - 1
  139.  
  140. queue = Queue()
  141. current_vertice = vertice
  142. current_offset_x = offset_x
  143. current_offset_y = offset_y
  144.  
  145. result = {}
  146.  
  147. while True:
  148. # узкое место, подсчёт ширины для каждого потомка
  149. current_x = current_offset_x + calculate_width(current_vertice['left'])
  150. current_y = current_offset_y
  151. result[current_vertice['id']] = ( current_x, current_y )
  152.  
  153. left = current_vertice['left']
  154. right = current_vertice['right']
  155.  
  156. current_offset_y = current_offset_y - 1
  157.  
  158. if left != None:
  159. if right != None:
  160. queue.put(( right, current_x + 1, current_offset_y ))
  161. current_vertice = left
  162. elif right != None:
  163. current_offset_x = current_x + 1
  164. current_vertice = right
  165. elif not queue.empty():
  166. current_vertice, current_offset_x, current_offset_y = queue.get()
  167. else:
  168. return result
  169.  
  170. # получаем координаты вершины
  171. def get_position_of(vertice, id):
  172. if vertice == None: return None
  173.  
  174. # если координаты ещё не были рассчитаны, рассчитаем
  175. if not 'x' in vertice: calculate_positions(vertice)
  176.  
  177. queue = Queue()
  178. current_vertice = vertice
  179.  
  180. while True:
  181. if current_vertice['id'] == id: return current_vertice['x'], current_vertice['y']
  182.  
  183. left = current_vertice['left']
  184. right = current_vertice['right']
  185.  
  186. if left != None:
  187. current_vertice = left
  188. if right != None:
  189. queue.put(right)
  190. elif right != None:
  191. current_vertice = right
  192. elif not queue.empty():
  193. current_vertice = queue.get()
  194. else:
  195. return None
  196.  
  197. def program():
  198. # читаем из stdin описание графа
  199. input_list = []
  200. edges_number = None
  201. tests_number = None
  202.  
  203. for line in sys.stdin:
  204. if line == None:
  205. print("error: unexpected EOF")
  206. return
  207.  
  208. if len(line) == 0:
  209. continue
  210.  
  211. splitted = [ int(item) for item in line.split() ]
  212.  
  213. # проверка входных данных
  214. if len(splitted) != (3 if edges_number == None else 2):
  215. print("error: not enough numbers: " + str(len(splitted)))
  216. return
  217.  
  218. if edges_number == None:
  219. # первая строка
  220. edges_number = splitted[0] - 1
  221. tests_number = splitted[2]
  222.  
  223. input_list.append(splitted)
  224.  
  225. # читаем лишь первую строку и все рёбра
  226. if len(input_list) == edges_number + 1:
  227. break
  228.  
  229. # создаём граф
  230. root_vertice = solve_graph(input_list)
  231. positions = calculate_positions(root_vertice)
  232.  
  233. # читаем вводимые с клавиатуры данные и сразу выводим результат
  234. for line in sys.stdin:
  235. if line == None:
  236. return
  237.  
  238. if len(line) == 0:
  239. continue
  240.  
  241. required_id = int(line)
  242. position = positions[required_id]
  243. print(str(position[0]) + " " + str(position[1]))
  244.  
  245. tests_number = tests_number - 1
  246. if tests_number == 0:
  247. break
  248.  
  249. program()
Advertisement
Add Comment
Please, Sign In to add comment