2008D.md (2185B)
1 Source: https://codeforces.com/problemset/problem/2008/D 2 3 D. Sakurako's Hobby 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 For a certain permutation $p$$^{\text{∗}}$ Sakurako calls an integer $j$ reachable from an integer $i$ if it is possible to make $i$ equal to $j$ by assigning $i=p_i$ a certain number of times. 22 23 If $p=[3,5,6,1,2,4]$, then, for example, $4$ is reachable from $1$, because: $i=1$ $\rightarrow$ $i=p_1=3$ $\rightarrow$ $i=p_3=6$ $\rightarrow$ $i=p_6=4$. Now $i=4$, so $4$ is reachable from $1$. 24 25 Each number in the permutation is colored either black or white. 26 27 Sakurako defines the function $F(i)$ as the number of black integers that are reachable from $i$. 28 29 Sakurako is interested in $F(i)$ for each $1\le i\le n$, but calculating all values becomes very difficult, so she asks you, as her good friend, to compute this. 30 31 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (the number $2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$, but the array contains $4$). 32 33 Input 34 35 The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. 36 37 The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of elements in the array. 38 39 The second line of each test case contains $n$ integers $p_1, p_2, \dots, p_n$ ($1\le p_i\le n$) — the elements of the permutation. 40 41 The third line of each test case contains a string $s$ of length $n$, consisting of '0' and '1'. If $s_i=0$, then the number $p_i$ is colored black; if $s_i=1$, then the number $p_i$ is colored white. 42 43 It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$. 44 45 Output 46 47 For each test case, output $n$ integers $F(1), F(2), \dots, F(n)$. 48 49 Example 50 51 Input 52 53 ``` 54 5 55 56 1 57 58 1 59 60 0 61 62 5 63 64 1 2 4 5 3 65 66 10101 67 68 5 69 70 5 4 1 3 2 71 72 10011 73 74 6 75 76 3 5 6 1 2 4 77 78 010000 79 80 6 81 82 1 2 3 4 5 6 83 84 100110 85 ``` 86 87 Output 88 89 ``` 90 1 91 0 1 1 1 1 92 2 2 2 2 2 93 4 1 4 4 1 4 94 0 1 1 0 0 1 95 ```