← 返回题目列表

AtCoder · abc437_e

E. 对数组进行排序

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

有 N+1 序列 A_0, A_1, \ldots, A_{N}. A_i 定义如下:

  • A_0 是一个空序列。
  • A_i\ (1\leq i\leq N) 是通过附加整数获得的序列 y_i 到序列末尾 A_{x_i}\ (0\leq x_i\lt i).

求排列 P=(P_1, P_2,\ldots,P_N) of (1,2,\ldots,N) 满足以下条件:

  • 对于 i = 1,2,\ldots,N-1,以下条件之一成立:
    • A_{P_i} 按字典顺序小于 A_{P_{i+1}}.
    • A_{P_i}= A_{P_{i+1}} 和 P_i\lt P_{i+1}

换句话说,当 A_1,A_2,\ldots,A_N 按字典顺序排列(当有多个相等序列时,先排列索引较小的序列), P 是该排列中出现的索引序列。

序列的字典顺序是什么?

一个序列 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序较小 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 如果满足以下两个条件之一。 在这里, |S| 和 |T| 代表的长度 S 和 T。

  1. |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两者成立:
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
    • S_i (在数值上)小于 T_i.

约束

  • 1\leq N\leq 3\times 10^5
  • 0\leq x_i\lt i
  • 1\leq y_i\leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
x_1 y_1
x_2 y_2
\vdots
x_N y_N

输出

输出 P_1, P_2, \ldots, P_N 位于一行,以空格分隔。


示例输入 1

4
0 2
0 1
2 2
0 1

示例输出 1

2 4 3 1

A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1),所以 P=(2,4,3,1).


示例输入 2

5
0 1
0 1
0 1
0 1
0 1

示例输出 2

1 2 3 4 5

A_1 = A_2 = A_3 = A_4 = A_5 = (1).


示例输入 3

10
0 305186313
1 915059758
0 105282054
1 696409999
3 185928366
3 573289179
6 254538849
3 105282054
5 696409999
8 168629803

示例输出 3

3 8 10 5 9 6 7 1 4 2