Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # coding: utf-8
- import sys
- from queue import *
- # строим граф из входных данных
- def solve_graph(input_list):
- vertices_number = input_list[0][0]
- root_id = input_list[0][1]
- edges_number = vertices_number - 1
- vertices = []
- for i in range(0, vertices_number):
- vertices.append({ 'id': i, 'left': None, 'right': None })
- root_vertice = vertices[root_id]
- # создаём таблицу «ID вершины → список соседей»
- # для больших деревьев с ней где-то в ≈310 раз быстрее
- edges = {}
- for i in range(1, edges_number + 1):
- entry = input_list[i]
- if entry[0] in edges:
- edges[entry[0]].append(entry[1])
- else:
- edges[entry[0]] = [ entry[1] ]
- if entry[1] in edges:
- edges[entry[1]].append(entry[0])
- else:
- edges[entry[1]] = [ entry[0] ]
- arrange_children_wrapper = None
- # распихаем потомков по слотам
- def arrange_children(vertice, vertice_parent_id):
- vertice_id = vertice['id']
- # добавляем потомка в незанятый слот
- def add_child(child):
- if vertice['left'] == None:
- vertice['left'] = child
- else:
- vertice['right'] = child
- # быстренько выдёргиваем соседей из той таблицы
- if vertice_id in edges:
- for i in edges[vertice_id]:
- if i != vertice_parent_id:
- add_child(vertices[i])
- # без рекурсии
- queue = Queue()
- current_vertice = root_vertice
- current_parent_id = -1
- while True:
- arrange_children(current_vertice, current_parent_id)
- left = current_vertice['left']
- right = current_vertice['right']
- current_parent_id = current_vertice['id']
- if left != None:
- current_vertice = left
- if right != None:
- queue.put(( right, current_parent_id ))
- elif right != None:
- current_vertice = right
- elif not queue.empty():
- current_vertice, current_parent_id = queue.get()
- else:
- break
- return root_vertice
- # размер графа (пусть и пострашнее, зато теперь без рекурсии)
- def calculate_width(vertice):
- if vertice == None: return 0
- queue = Queue()
- current_vertice = vertice
- width = 0
- while True:
- width = width + 1
- left = current_vertice['left']
- right = current_vertice['right']
- if left != None:
- current_vertice = left
- if right != None:
- queue.put(right)
- elif right != None:
- current_vertice = right
- elif not queue.empty():
- current_vertice = queue.get()
- else:
- return width
- def calculate_height(vertice):
- if vertice == None: return 0
- queue = Queue()
- current_vertice = vertice
- current_height = 0
- height = 0
- while True:
- current_height = current_height + 1
- height = max(height, current_height)
- left = current_vertice['left']
- right = current_vertice['right']
- if left != None:
- current_vertice = left
- if right != None:
- queue.put(( right, current_height ))
- elif right != None:
- current_vertice = right
- elif not queue.empty():
- current_vertice, current_height = queue.get()
- else:
- return height
- def calculate_size(vertice):
- return calculate_width(vertice), calculate_height(vertice)
- # рекурсивный расчёт координат вершин
- def calculate_positions(vertice, offset_x = 0, offset_y = -1):
- if vertice == None: return
- # зачем-то ось Y направлена вверх, «против» графа, так что начнём отсчёт с
- # высоты и пойдём наверх
- if offset_y == -1: offset_y = calculate_height(vertice) - 1
- queue = Queue()
- current_vertice = vertice
- current_offset_x = offset_x
- current_offset_y = offset_y
- while True:
- # узкое место, подсчёт ширины для каждого потомка
- current_vertice['x'] = current_offset_x + calculate_width(current_vertice['left'])
- current_vertice['y'] = current_offset_y
- left = current_vertice['left']
- right = current_vertice['right']
- current_offset_y = current_offset_y - 1
- if left != None:
- if right != None:
- queue.put(( right, current_vertice['x'] + 1, current_offset_y ))
- current_vertice = left
- elif right != None:
- current_offset_x = current_vertice['x'] + 1
- current_vertice = right
- elif not queue.empty():
- current_vertice, current_offset_x, current_offset_y = queue.get()
- else:
- return
- # красивенький вывод
- # рекурсивен, так что не работает для больших деревьев
- def print_in_order(vertice):
- # если координаты ещё не были рассчитаны, рассчитаем
- if not 'x' in vertice: calculate_positions(vertice)
- # размер графа
- width, height = calculate_size(vertice)
- if width > 120:
- print('graph is too big')
- return
- # создаём поле из «-1» размером с граф
- field = [ [ -1 for x in range(0, width) ] for x in
- list(range(0, calculate_height(vertice))) ]
- # рекурсивно отмечаем вершину на поле
- def mark_vertice(vertice):
- if vertice == None: return
- # опять же, переворачиваем ось Y
- field[height - 1 - vertice['y']][vertice['x']] = vertice['id']
- mark_vertice(vertice['left'])
- mark_vertice(vertice['right'])
- mark_vertice(vertice)
- # выводим поле (с пробелами вместо «-1»)
- print('\n'.join(''.join(
- ' ' if x == -1 else str(x) for x in y) for y in field))
- # получаем координаты вершины
- def get_position_of(vertice, id):
- if vertice == None: return None
- # если координаты ещё не были рассчитаны, рассчитаем
- if not 'x' in vertice: calculate_positions(vertice)
- queue = Queue()
- current_vertice = vertice
- while True:
- if current_vertice['id'] == id: return current_vertice['x'], current_vertice['y']
- left = current_vertice['left']
- right = current_vertice['right']
- if left != None:
- current_vertice = left
- if right != None:
- queue.put(right)
- elif right != None:
- current_vertice = right
- elif not queue.empty():
- current_vertice = queue.get()
- else:
- return None
- def program():
- # читаем из stdin описание графа
- input_list = []
- edges_number = None
- tests_number = None
- for line in sys.stdin:
- if line == None:
- print("error: unexpected EOF")
- return
- if len(line) == 0:
- continue
- splitted = [ int(item) for item in line.split() ]
- # проверка входных данных
- if len(splitted) != (3 if edges_number == None else 2):
- print("error: not enough numbers: " + str(len(splitted)))
- return
- if edges_number == None:
- # первая строка
- edges_number = splitted[0] - 1
- tests_number = splitted[2]
- input_list.append(splitted)
- # читаем лишь первую строку и все рёбра
- if len(input_list) == edges_number + 1:
- break
- # создаём граф
- root_vertice = solve_graph(input_list)
- # выводим для отладки
- # print_in_order(root_vertice)
- # читаем вводимые с клавиатуры данные и сразу выводим результат
- for line in sys.stdin:
- if line == None:
- return
- if len(line) == 0:
- continue
- required_id = int(line)
- position = get_position_of(root_vertice, required_id)
- print(str(position[0]) + " " + str(position[1]))
- tests_number = tests_number - 1
- if tests_number == 0:
- break
- program()
Advertisement
Add Comment
Please, Sign In to add comment