Untitled

 avatar
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...