Submission #65275571

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:
    __slots__ = ('next','terminal','sub_cnt')
    def __init__(self):
        self.next = {}
        self.terminal=False
        self.sub_cnt=0
X_root=TrieNode()
Y_root=TrieNode()
total=0
def insert_X(s):
    node = X_root
    for c in s:
        node=node.next.setdefault(c, TrieNode())
    node.terminal=True
    path = []
    u = Y_root
    for c in s:
        if c not in u.next:
            return
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

class TrieNode:
    __slots__ = ('next','terminal','sub_cnt')
    def __init__(self):
        self.next = {}
        self.terminal=False
        self.sub_cnt=0

X_root=TrieNode()
Y_root=TrieNode()
total=0

def insert_X(s):
    node = X_root
    for c in s:
        node=node.next.setdefault(c, TrieNode())
    node.terminal=True
    path = []
    u = Y_root
    for c in s:
        if c not in u.next:
            return
        path.append((u,c))
        u = u.next[c]
    k = u.sub_cnt
    if k == 0:
        return
    global total
    total-=k
    for (parent, ch) in path:
        parent.sub_cnt-=k
    parent,ch=path[-1]
    del parent.next[ch]

def insert_Y(s):

    node = X_root
    for c in s:
        if node.terminal:
            return
        if c not in node.next:
            break
        node = node.next[c]
    if node.terminal:
        return

    u=Y_root
    u.sub_cnt += 1
    for c in s:
        u = u.next.setdefault(c, TrieNode())
        u.sub_cnt+=1

    global total
    total+=1

Q=int(input())
for _ in range(Q):
    t, s = input().split()
    t=int(t)
    if t == 1:
        insert_X(s)
    else:
        insert_Y(s)
    print(total)

Submission Info

Judge Result