gmo61520

Untitled

Mar 12th, 2016
199
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.80 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. def calculate_size(vertice):
  133. return calculate_width(vertice), calculate_height(vertice)
  134.  
  135. # рекурсивный расчёт координат вершин
  136. def calculate_positions(vertice, offset_x = 0, offset_y = -1):
  137. if vertice == None: return
  138.  
  139. # зачем-то ось Y направлена вверх, «против» графа, так что начнём отсчёт с
  140. # высоты и пойдём наверх
  141. if offset_y == -1: offset_y = calculate_height(vertice) - 1
  142.  
  143. queue = Queue()
  144. current_vertice = vertice
  145. current_offset_x = offset_x
  146. current_offset_y = offset_y
  147.  
  148. while True:
  149. # узкое место, подсчёт ширины для каждого потомка
  150. current_vertice['x'] = current_offset_x + calculate_width(current_vertice['left'])
  151. current_vertice['y'] = current_offset_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_vertice['x'] + 1, current_offset_y ))
  161. current_vertice = left
  162. elif right != None:
  163. current_offset_x = current_vertice['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
  169.  
  170. # красивенький вывод
  171. # рекурсивен, так что не работает для больших деревьев
  172. def print_in_order(vertice):
  173. # если координаты ещё не были рассчитаны, рассчитаем
  174. if not 'x' in vertice: calculate_positions(vertice)
  175.  
  176. # размер графа
  177. height = calculate_height(vertice)
  178. width = calculate_width(vertice)
  179.  
  180. if width > 120:
  181. print('graph is too big')
  182. return
  183.  
  184. # создаём поле из «-1» размером с граф
  185. field = [ [ -1 for x in range(0, width) ] for x in
  186. list(range(0, calculate_height(vertice))) ]
  187.  
  188. # рекурсивно отмечаем вершину на поле
  189. def mark_vertice(vertice):
  190. if vertice == None: return
  191.  
  192. # опять же, переворачиваем ось Y
  193. field[height - 1 - vertice['y']][vertice['x']] = vertice['id']
  194. mark_vertice(vertice['left'])
  195. mark_vertice(vertice['right'])
  196.  
  197. mark_vertice(vertice)
  198.  
  199. # выводим поле (с пробелами вместо «-1»)
  200. print('\n'.join(''.join(
  201. ' ' if x == -1 else str(x) for x in y) for y in field))
  202.  
  203. # получаем координаты вершины
  204. def get_position_of(vertice, id):
  205. if vertice == None: return None
  206.  
  207. # если координаты ещё не были рассчитаны, рассчитаем
  208. if not 'x' in vertice: calculate_positions(vertice)
  209.  
  210. queue = Queue()
  211. current_vertice = vertice
  212.  
  213. while True:
  214. if current_vertice['id'] == id: return current_vertice['x'], current_vertice['y']
  215.  
  216. left = current_vertice['left']
  217. right = current_vertice['right']
  218.  
  219. if left != None:
  220. current_vertice = left
  221. if right != None:
  222. queue.put(right)
  223. elif right != None:
  224. current_vertice = right
  225. elif not queue.empty():
  226. current_vertice = queue.get()
  227. else:
  228. return None
  229.  
  230. def program():
  231. # читаем из stdin описание графа
  232. input_list = []
  233. edges_number = None
  234. tests_number = None
  235.  
  236. for line in sys.stdin:
  237. if line == None:
  238. print("error: unexpected EOF")
  239. return
  240.  
  241. if len(line) == 0:
  242. continue
  243.  
  244. splitted = [ int(item) for item in line.split() ]
  245.  
  246. # проверка входных данных
  247. if len(splitted) != (3 if edges_number == None else 2):
  248. print("error: not enough numbers: " + str(len(splitted)))
  249. return
  250.  
  251. if edges_number == None:
  252. # первая строка
  253. edges_number = splitted[0] - 1
  254. tests_number = splitted[2]
  255.  
  256. input_list.append(splitted)
  257.  
  258. # читаем лишь первую строку и все рёбра
  259. if len(input_list) == edges_number + 1:
  260. break
  261.  
  262. # создаём граф
  263. root_vertice = solve_graph(input_list)
  264.  
  265. # выводим для отладки
  266. # print_in_order(root_vertice)
  267.  
  268. # читаем вводимые с клавиатуры данные и сразу выводим результат
  269. for line in sys.stdin:
  270. if line == None:
  271. return
  272.  
  273. if len(line) == 0:
  274. continue
  275.  
  276. required_id = int(line)
  277. position = get_position_of(root_vertice, required_id)
  278. print(str(position[0]) + " " + str(position[1]))
  279.  
  280. tests_number = tests_number - 1
  281. if tests_number == 0:
  282. break
  283.  
  284. program()
Advertisement
Add Comment
Please, Sign In to add comment