Untitled
unknown
python
2 years ago
3.2 kB
14
Indexable
import math class Node: def __init__(self, val): self.val = val self.uid = None self.parent = None self.children = [] self.isLocked = False self.isDescendantLocked = 0 class Tree: def __init__(self, n, m, node_lst, queries): self.node_lst = [] self.node_map = {} for node in node_lst: converted = Node(node) self.node_lst.append(converted) self.node_map[node] = converted for i in range(int(n/m)): start = i*m + 1 end = i*m + m if end > n-1: end -= end%(n-1) if end < n: self.node_lst[i].children = self.node_lst[start: end+1] for i in range(1, n): self.node_lst[i].parent = self.node_lst[math.ceil(i/m) - 1] self.root = self.node_lst[0] self.processed_queries = [query.split() for query in queries] def lock(self, node, uid): if node.isDescendantLocked>0 or node.isLocked or self.isAncestorLocked(node.parent): return False node.uid = uid node.isLocked = True parent_node = node.parent while parent_node: parent_node.isDescendantLocked += 1 parent_node = parent_node.parent return True def unlock(self, node, uid): if uid != node.uid or not node.isLocked: return False node.isLocked = False node.uid = None parent_node = node.parent while parent_node: parent_node.isDescendantLocked -= 1 parent_node = parent_node.parent return True def upgrade(self, node, uid): if node.isDescendantLocked == 0 or self.isAncestorLocked(node.parent): return False self.unlockChildren(node, uid) self.lock(node, uid) return True def isAncestorLocked(self, node): while node: if node.isLocked: return True node = node.parent return False def unlockChildren(self, node, uid): for child in node.children: self.unlock(child, uid) self.unlockChildren(child, uid) if __name__ == '__main__': n = int(input()) m = int(input()) q = int(input()) nodes = [] queries = [] for i in range(n): nodes.append(str(input())) for i in range(q): queries.append(str(input())) obj = Tree(n, m, nodes, queries) for query in obj.processed_queries: if query[0] == "1": if obj.lock(obj.node_map[query[1]], query[2]): print('true') else: print('false') elif query[0] == "2": if obj.unlock(obj.node_map[query[1]], query[2]): print('true') else: print('false') elif query[0] == "3": if obj.upgrade(obj.node_map[query[1]], query[2]): print('true') else: print('false')
Editor is loading...