提出 #71867601

---

ソースコード 拡げる

import sys

sys.setrecursionlimit(300000)
input = sys.stdin.readline


N = int(input())


# node_adj[u] = {value:child_node_index,...}
node_adj = [{}]
node_indices = [[]]

# input_to_trie[x] = TrieNodeIndex
input_to_trie = [0] * (N + 1)

# A0 は空列 (Trieのルート: index 0)
# A1...AN を順にTrieに追加していく
for i in range(1, N + 1):
    xi, yi = map(int, input().split())
    
    # 親となるTrieノードを取得
    parent_node = input_to_trie[xi]
    if yi in node_adj[parent_node]:
        #既存のノードへ移動（数列の内容が同じになるケース）
        curr_node = node_adj[parent_node][yi]
    else:
        # 新しいノードを作成
        curr_node = len(node_adj)
        node_adj.append({})
        node_indices.append([])
        node_adj[parent_node][yi] = curr_node

    node_indices[curr_node].append(i)
    #マッピングを保存
    input_to_trie[i] = curr_node

ans = []


def dfs(u):
    for idx in node_indices[u]:
        ans.append(idx)
    
    sorted_keys = sorted(node_adj[u].keys())
    
    for key in sorted_keys:
        next_node = node_adj[u][key]
        dfs(next_node)

# ルート(0)から探索開始
dfs(0)
print(*ans)

提出情報

ジャッジ結果