Submission #1078618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078618		xinyubb2000	Vlak (COCI20_vlak)	Cpython 3	70 / 70	501 ms	52824 KiB

Main

class TrieNode:
    def __init__(self):
        # 使用字典存储子节点
        self.children = {}
        # 标记是否是一个完整的单词
        self.is_end_of_word = False
        self.prefix = ""

class Trie:
    def __init__(self):
        # 根节点是一个空的 TrieNode
        self.root = TrieNode()
        self.root.prefix = "root"

    def insert(self, word: str) -> None:
        # 从根节点开始
        node = self.root
        prefix = ""
        for char in word:
            prefix += char
            # 如果字符不在当前节点的子节点中，创建一个新的子节点
            if char not in node.children:
                node.children[char] = TrieNode()
                node.children[char].prefix = prefix
            # 移动到子节点
            node = node.children[char]
        # 插入完成后，标记最后一个节点为完整单词
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        # 从根节点开始
        node = self.root
        for char in word:
            # 如果字符不在子节点中，说明单词不存在
            if char not in node.children:
                return False
            # 移动到子节点
            node = node.children[char]
        # 返回是否为完整单词
        return node.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        # 从根节点开始
        node = self.root
        for char in prefix:
            # 如果字符不在子节点中，说明前缀不存在
            if char not in node.children:
                return False
            # 移动到子节点
            node = node.children[char]
        # 所有字符都在子节点中，说明存在该前缀
        return True

# import sys

# sys.stdin = open('2.in', 'r')

tries = [Trie(), Trie()]

for i in range(2):
    n = int(input())
    for _ in range(n):
        tries[i].insert(input())

def solve(nodes, char, who):
    # print("ch:", char, nodes[0].prefix, nodes[1].prefix, 'who:', who)

    if char not in nodes[0].children or len(nodes[0].children[char].children) == 0:
        # print(who, 'False')
        return False
    
    next_who = 'N' if who == 'E' else 'E'
    for next_ch, next_node in nodes[0].children[char].children.items():
        if not solve([nodes[1], next_node], next_ch, next_who):
            # print(who, 'True')
            return True
    # print(who, 'False')
    return False

Nina = TrieNode()
Nina.children['N'] = tries[0].root
Nina.prefix = "Nina"
print('Nina' if solve([Nina, tries[1].root], 'N', 'N') else 'Emilija')

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10