Submission #1079955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079955		xinyubb2000	Type Printer (IOI08_printer)	Cpython 3	80 / 100	1091 ms	157008 KiB

printer

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 / 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
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10