oj.uz

Submission #1078619

# Submission time Handle Problem Language Result Execution time Memory
1078619 2024-08-28T00:32:12 Z xinyubb2000 Vlak (COCI20_vlak) Python 3
70 / 70
 383 ms 42580 KB 
class TrieNode:
    def __init__(self):
        # 使用字典存储子节点
        self.children = {}
        # 标记是否是一个完整的单词
        self.is_end_of_word = False

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

    def insert(self, word: str) -> None:
        # 从根节点开始
        node = self.root
        for char in word:
            # 如果字符不在当前节点的子节点中，创建一个新的子节点
            if char not in node.children:
                node.children[char] = TrieNode()
            # 移动到子节点
            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):
    if char not in nodes[0].children or len(nodes[0].children[char].children) == 0:
        return False
    
    for next_ch, next_node in nodes[0].children[char].children.items():
        if not solve([nodes[1], next_node], next_ch):
            return True

    return False

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3420 KB Output is correct
2 Correct 13 ms 3420 KB Output is correct
3 Correct 12 ms 3548 KB Output is correct
4 Correct 14 ms 3420 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3420 KB Output is correct
2 Correct 13 ms 3424 KB Output is correct
3 Correct 13 ms 3420 KB Output is correct
4 Correct 13 ms 3536 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3420 KB Output is correct
2 Correct 14 ms 3528 KB Output is correct
3 Correct 13 ms 3420 KB Output is correct
4 Correct 14 ms 3432 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 38856 KB Output is correct
2 Correct 267 ms 36436 KB Output is correct
3 Correct 241 ms 34644 KB Output is correct
4 Correct 315 ms 37716 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 40888 KB Output is correct
2 Correct 304 ms 42580 KB Output is correct
3 Correct 282 ms 39248 KB Output is correct
4 Correct 262 ms 39948 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 37972 KB Output is correct
2 Correct 236 ms 37204 KB Output is correct
3 Correct 270 ms 38300 KB Output is correct
4 Correct 321 ms 40276 KB Output is correct