gmo61520

Untitled

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