1968D.md (3131B)
1 Source: https://codeforces.com/problemset/problem/1968/D 2 3 D. Permutation Game 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 Bodya and Sasha found a permutation $p_1,\dots,p_n$ and an array $a_1,\dots,a_n$. They decided to play a well-known "Permutation game". 22 23 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 ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 24 25 Both of them chose a starting position in the permutation. 26 27 The game lasts $k$ turns. The players make moves simultaneously. On each turn, two things happen to each player: 28 29 * If the current position of the player is $x$, his score increases by $a_x$. 30 * Then the player either stays at his current position $x$ or moves from $x$ to $p_x$. 31 32 The winner of the game is the player with the higher score after exactly $k$ turns. 33 34 Knowing Bodya's starting position $P_B$ and Sasha's starting position $P_S$, determine who wins the game if both players are trying to win. 35 36 Input 37 38 The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of testcases. 39 40 The first line of each testcase contains integers $n$, $k$, $P_B$, $P_S$ ($1\le P_B,P_S\le n\le 2\cdot 10^5$, $1\le k\le 10^9$) — length of the permutation, duration of the game, starting positions respectively. 41 42 The next line contains $n$ integers $p_1,\dots,p_n$ ($1 \le p_i \le n$) — elements of the permutation $p$. 43 44 The next line contains $n$ integers $a_1,\dots,a_n$ ($1\le a_i\le 10^9$) — elements of array $a$. 45 46 It is guaranteed that the sum of values of $n$ over all test cases does not exceed $2 \cdot 10^5$. 47 48 Output 49 50 For each testcase output: 51 52 * "Bodya" if Bodya wins the game. 53 * "Sasha" if Sasha wins the game. 54 * "Draw" if the players have the same score. 55 56 Example 57 58 Input 59 60 ``` 61 10 62 63 4 2 3 2 64 65 4 1 2 3 66 67 7 2 5 6 68 69 10 8 2 10 70 71 3 1 4 5 2 7 8 10 6 9 72 73 5 10 5 1 3 7 10 15 4 3 74 75 2 1000000000 1 2 76 77 1 2 78 79 4 4 80 81 8 10 4 1 82 83 5 1 4 3 2 8 6 7 84 85 1 1 2 1 2 100 101 102 86 87 5 1 2 5 88 89 1 2 4 5 3 90 91 4 6 9 4 2 92 93 4 2 3 1 94 95 4 1 3 2 96 97 6 8 5 3 98 99 6 9 5 4 100 101 6 1 3 5 2 4 102 103 6 9 8 9 5 10 104 105 4 8 4 2 106 107 2 3 4 1 108 109 5 2 8 7 110 111 4 2 3 1 112 113 4 1 3 2 114 115 6 8 5 3 116 117 2 1000000000 1 2 118 119 1 2 120 121 1000000000 2 122 ``` 123 124 Output 125 126 ``` 127 Bodya 128 Sasha 129 Draw 130 Draw 131 Bodya 132 Sasha 133 Sasha 134 Sasha 135 Sasha 136 Bodya 137 ``` 138 139 Note 140 141 Below you can find the explanation for the first testcase, where the game consists of $k=2$ turns. 142 143 | | | | | | | | 144 | --- | --- | --- | --- | --- | --- | --- | 145 | Turn | Bodya's position | Bodya's score | Bodya's move | Sasha's position | Sasha's score | Sasha's move | 146 | first | $3$ | $0 + a_3 = 0 + 5 = 5$ | stays on the same position | $2$ | $0 + a_2 = 0 + 2 = 2$ | moves to $p_2=1$ | 147 | second | $3$ | $5 + a_3 = 5 + 5 = 10$ | stays on the same position | $1$ | $2 + a_1 = 2 + 7 = 9$ | stays on the same position | 148 | final results | $3$ | $10$ | | $1$ | $9$ | | 149 150 As we may see, Bodya's score is greater, so he wins the game. It can be shown that Bodya always can win this game.