codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```