# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1078619 |
2024-08-28T00:32:12 Z |
xinyubb2000 |
Vlak (COCI20_vlak) |
Python 3 |
|
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')
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |