oj.uz

답안 #1079948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1079948 2024-08-29T04:50:01 Z xinyubb2000 Type Printer (IOI08_printer) Python 3
0 / 100
 882 ms 64816 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

def dfs2(node):
    if node.is_end_of_word:
        print('P')
        global cnt
        cnt += 1
        if cnt == n:
            exit()

    for char, child in sorted(node.children.items(), key=lambda item: item[1].depth):
        print(char)
        dfs2(child)
        print('-')

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 2908 KB Expected integer, but "t" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 2908 KB Expected integer, but "n" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 2908 KB Expected integer, but "h" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 2908 KB Expected integer, but "t" found
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 3164 KB Expected integer, but "w" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 5468 KB Expected integer, but "v" found
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 12368 KB Expected integer, but "r" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 249 ms 27304 KB Expected integer, but "x" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 882 ms 64816 KB Expected integer, but "v" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 758 ms 49612 KB Expected integer, but "p" found
2 Halted 0 ms 0 KB -