oj.uz

Submission #1079955

# Submission time Handle Problem Language Result Execution time Memory
1079955 2024-08-29T04:55:57 Z xinyubb2000 Type Printer (IOI08_printer) Python 3
80 / 100
 1000 ms 157008 KB 
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False
        self.depth = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    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 starts_with(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('1.in', 'r')

trie = Trie()

n = int(input())
for _ in range(n):
    word = input()
    trie.insert(word)

cnt = 0

def dfs1(node):
    depth = 0
    for child in node.children.values():
        depth = max(depth, dfs1(child))

    node.depth = depth + 1
    return node.depth

res = []
def dfs2(node):
    if node.is_end_of_word:
        res.append('P')
        global cnt
        cnt += 1

    for char, child in sorted(node.children.items(), key=lambda item: item[1].depth):
        res.append(char)
        dfs2(child)
        if cnt < n:
            res.append('-')

dfs1(trie.root)
dfs2(trie.root)

print(len(res))
print(*res, sep='\n')

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2908 KB Output is correct
2 Correct 10 ms 2924 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2908 KB Output is correct
2 Correct 11 ms 2908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2908 KB Output is correct
2 Correct 12 ms 3092 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2908 KB Output is correct
2 Correct 13 ms 2908 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3164 KB Output is correct
2 Correct 21 ms 4700 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5980 KB Output is correct
2 Correct 36 ms 6744 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 13844 KB Output is correct
2 Correct 175 ms 26412 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 30508 KB Output is correct
2 Correct 77 ms 8984 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 72548 KB Output is correct
2 Execution timed out 1074 ms 146280 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 56036 KB Output is correct
2 Execution timed out 1091 ms 157008 KB Time limit exceeded
3 Halted 0 ms 0 KB -