/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
(1,2,\ldots,N) の並べ替え P=(P _ 1,P _ 2,\ldots,P _ N),A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。
あなたは、次の操作を 0 回以上好きな回数行うことができます。
- i=1,2,\ldots,N に対して一斉に A _ i を A _ {P _ i} で置き換える。
得られる A としてありえるもののうち、辞書順で最小のものを出力してください。
辞書順の大小とは？
長さ N の列 A=(A _ 1,A _ 2,\ldots,A _ N),B=(B _ 1,B _ 2,\ldots,B _ N) について、辞書順で A が B より小さいとは、次のことが成り立つことをいいます。
- ある整数 i\ (1\leq i\leq N) が存在し、A _ i\lt B _ i が成り立ち、1\leq j\lt i を満たすすべての整数 j に対して A _ j=B _ j が成り立つ。
制約
- 1\leq N\leq2\times10 ^ 5
- 1\leq P _ i\leq N\ (1\leq i\leq N)
- P _ i\neq P _ j\ (1\leq i\lt j\leq N)
- 1\leq A _ i\leq N\ (1\leq i\leq N)
- A _ i\neq A _ j\ (1\leq i\lt j\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P _ 1 P _ 2 \ldots P _ N A _ 1 A _ 2 \ldots A _ N
出力
0 回以上の操作の結果としてあり得る A のうち辞書順で最小のものを (A _ 1,A _ 2,\ldots,A _ N) として、A _ 1,A _ 2,\ldots,A _ N をこの順に空白を区切りとして 1 行に出力せよ。
入力例 1
6 3 1 5 6 2 4 4 3 1 6 2 5
出力例 1
1 4 2 5 3 6
はじめ、A=(4,3,1,6,2,5) です。
ここから操作を繰り返すと、以下のようになります。
- A=(1,4,2,5,3,6) となる。
- A=(2,1,3,6,4,5) となる。
- A=(3,2,4,5,1,6) となる。
- A=(4,3,1,6,2,5) となる。
以降、4 回操作を行うたびにもとの A に戻ります。
よって、このうち辞書順で最小である 1 4 2 5 3 6 を出力してください。
入力例 2
8 3 5 8 7 2 6 1 4 1 2 3 4 5 6 7 8
出力例 2
1 2 3 4 5 6 7 8
1 度も操作をしなくても構いません。
入力例 3
26 24 14 4 20 15 19 16 11 23 22 12 18 21 3 6 8 26 2 25 7 13 1 5 9 17 10 15 3 10 1 13 19 22 24 20 4 14 23 7 26 25 18 11 6 9 12 2 21 5 16 8 17
出力例 3
4 1 22 18 20 13 14 6 15 11 3 26 2 12 5 23 9 10 25 24 7 17 16 21 19 8
Score : 575 points
Problem Statement
You are given permutations P = (P_1, P_2, \ldots, P_N) and A = (A_1, A_2, \ldots, A_N) of (1,2,\ldots,N).
You can perform the following operation any number of times, possibly zero:
- replace A_i with A_{P_i} simultaneously for all i=1,2,\ldots,N.
Print the lexicographically smallest A that can be obtained.
What is lexicographical order?
For sequences of length N, A = (A_1, A_2, \ldots, A_N) and B = (B_1, B_2, \ldots, B_N), A is lexicographically smaller than B if and only if:
- there exists an integer i\ (1\leq i\leq N) such that A_i < B_i, and A_j = B_j for all 1\leq j < i.
Constraints
- 1\leq N\leq2\times10^5
- 1\leq P_i\leq N\ (1\leq i\leq N)
- P_i\neq P_j\ (1\leq i<j\leq N)
- 1\leq A_i\leq N\ (1\leq i\leq N)
- A_i\neq A_j\ (1\leq i<j\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N A_1 A_2 \ldots A_N
Output
Let (A_1, A_2, \ldots, A_N) be the lexicographically smallest A that can be obtained. Print A_1, A_2, \ldots, A_N in this order, separated by spaces, in one line.
Sample Input 1
6 3 1 5 6 2 4 4 3 1 6 2 5
Sample Output 1
1 4 2 5 3 6
Initially, A = (4, 3, 1, 6, 2, 5).
Repeating the operation yields the following.
- A = (1, 4, 2, 5, 3, 6)
- A = (2, 1, 3, 6, 4, 5)
- A = (3, 2, 4, 5, 1, 6)
- A = (4, 3, 1, 6, 2, 5)
After this, A will revert to the original state every four operations.
Therefore, print the lexicographically smallest among these, which is 1 4 2 5 3 6.
Sample Input 2
8 3 5 8 7 2 6 1 4 1 2 3 4 5 6 7 8
Sample Output 2
1 2 3 4 5 6 7 8
You may choose to perform no operations.
Sample Input 3
26 24 14 4 20 15 19 16 11 23 22 12 18 21 3 6 8 26 2 25 7 13 1 5 9 17 10 15 3 10 1 13 19 22 24 20 4 14 23 7 26 25 18 11 6 9 12 2 21 5 16 8 17
Sample Output 3
4 1 22 18 20 13 14 6 15 11 3 26 2 12 5 23 9 10 25 24 7 17 16 21 19 8