oj.uz

Submission #1078618

# Submission time Handle Problem Language Result Execution time Memory
1078618 2024-08-28T00:30:27 Z xinyubb2000 Vlak (COCI20_vlak) Python 3
70 / 70
 501 ms 52824 KB 
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3932 KB Output is correct
2 Correct 13 ms 3676 KB Output is correct
3 Correct 13 ms 3668 KB Output is correct
4 Correct 13 ms 3644 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3624 KB Output is correct
2 Correct 13 ms 3552 KB Output is correct
3 Correct 14 ms 3676 KB Output is correct
4 Correct 13 ms 3504 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3420 KB Output is correct
2 Correct 16 ms 3644 KB Output is correct
3 Correct 14 ms 3384 KB Output is correct
4 Correct 18 ms 3420 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3436 KB Output is correct
2 Correct 15 ms 3420 KB Output is correct
3 Correct 14 ms 3672 KB Output is correct
4 Correct 15 ms 3420 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 45400 KB Output is correct
2 Correct 319 ms 43092 KB Output is correct
3 Correct 289 ms 40992 KB Output is correct
4 Correct 468 ms 44428 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 50916 KB Output is correct
2 Correct 356 ms 52824 KB Output is correct
3 Correct 329 ms 49236 KB Output is correct
4 Correct 330 ms 49660 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 45396 KB Output is correct
2 Correct 306 ms 44428 KB Output is correct
3 Correct 321 ms 45396 KB Output is correct
4 Correct 394 ms 48100 KB Output is correct