Submission #65261702

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class TrieNode:
    def __init__(self):
        self.child={}
        self.is_end=False
class Trie:
    def __init__(self):
        self.root=TrieNode()
        
    def insert(self, word):
        node=self.root
        for ch in word:
            if ch not in node.child:
                node.child[ch]=TrieNode()
            node = node.child[ch]
        node.is_end = True
    def match(self, word):
        node=self.root
        for ch in word:
            if ch not in node.child:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

class TrieNode:
    def __init__(self):
        self.child={}
        self.is_end=False

class Trie:
    def __init__(self):
        self.root=TrieNode()
        
    def insert(self, word):
        node=self.root
        for ch in word:
            if ch not in node.child:
                node.child[ch]=TrieNode()
            node = node.child[ch]
        node.is_end = True

    def match(self, word):
        node=self.root
        for ch in word:
            if ch not in node.child:
                return False
            node = node.child[ch]
            if node.is_end:
                return True
        return False

def solve(queries):
    trie=Trie()
    Y=[]
    y_good=[]
    count= 0

    result=[]

    for T, S in queries:
        if T==1:
            trie.insert(S)
            for i in range(len(Y)):
                if y_good[i] and trie.match(Y[i]):
                    y_good[i]=False
                    count-= 1
        else:
            f=trie.match(S)
            if not f:
                count+=1
            Y.append(S)
            y_good.append(not f)

        result.append(count)

    return result

Q=int(input())
queries=[]
for _ in range(Q):
    T,S=input().split()
    T = int(T)
    queries.append((T,S))

ans=solve(queries)
for a in ans:
    print(a)

Submission Info

Judge Result