codeforces-scrape

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

1851E.md (3325B)


      1 Source: https://codeforces.com/problemset/problem/1851/E
      2 
      3 E. Nastya and Potions
      4 
      5 time limit per test
      6 
      7 3 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 Alchemist Nastya loves mixing potions. There are a total of $n$ types of potions, and one potion of type $i$ can be bought for $c_i$ coins.
     22 
     23 Any kind of potions can be obtained in no more than one way, by mixing from several others. The potions used in the mixing process will be consumed. Moreover, no potion can be obtained from itself through one or more mixing processes.
     24 
     25 As an experienced alchemist, Nastya has an unlimited supply of $k$ types of potions $p_1, p_2, \dots, p_k$, but she doesn't know which one she wants to obtain next. To decide, she asks you to find, for each $1 \le i \le n$, the minimum number of coins she needs to spend to obtain a potion of type $i$ next.
     26 
     27 Input
     28 
     29 The first line of each test contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     30 
     31 Each test case is described as follows:
     32 
     33 The first line contains two integers $n$ and $k$ ($1 \le k \lt n \le 2 \cdot 10^5$) — the total number of potion types and the number of potion types Nastya already has.
     34 
     35 The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — the costs of buying the potions.
     36 
     37 The third line contains $k$ distinct integers $p_1, p_2, \dots, p_k$ ($1 \le p_i \le n$) — the indices of potions Nastya already has an unlimited supply of.
     38 
     39 This is followed by $n$ lines describing ways to obtain potions by mixing.
     40 
     41 Each line starts with the integer $m_i$ ($0 \le m_i \lt n$) — the number of potions required to mix a potion of the type $i$ ($1 \le i \le n$).
     42 
     43 Then line contains $m_i$ distinct integers $e_1, e_2, \dots, e_{m_i}$ ($1 \le e_j \le n$, $e_j \ne i$) — the indices of potions needed to mix a potion of the type $i$. If this list is empty, then a potion of the type $i$ can only be bought.
     44 
     45 It is guaranteed that no potion can be obtained from itself through one or more mixing processes.
     46 
     47 It is guaranteed that the sum of all $n$ values across all test cases does not exceed $2 \cdot 10^5$. Similarly, it is guaranteed that the sum of all $m_i$ values across all test cases does not exceed $2 \cdot 10^5$.
     48 
     49 Output
     50 
     51 For each test case, output $n$ integers — the minimum number of coins Nastya needs to spend to obtain a potion of each type.
     52 
     53 Examples
     54 
     55 Input
     56 
     57 ```
     58 4
     59 
     60 5 1
     61 
     62 30 8 3 5 10
     63 
     64 3
     65 
     66 3 2 4 5
     67 
     68 0
     69 
     70 0
     71 
     72 2 3 5
     73 
     74 0
     75 
     76 3 2
     77 
     78 5 143 3
     79 
     80 1 3
     81 
     82 1 2
     83 
     84 0
     85 
     86 2 1 2
     87 
     88 5 1
     89 
     90 5 4 1 3 4
     91 
     92 2
     93 
     94 2 4 5
     95 
     96 3 3 5 4
     97 
     98 2 1 4
     99 
    100 1 5
    101 
    102 0
    103 
    104 4 2
    105 
    106 1 1 5 4
    107 
    108 2 4
    109 
    110 3 2 4 3
    111 
    112 0
    113 
    114 2 2 4
    115 
    116 1 2
    117 ```
    118 
    119 Output
    120 
    121 ```
    122 23 8 0 5 10 
    123 0 143 0 
    124 5 0 1 3 4 
    125 0 0 0 0
    126 ```
    127 
    128 Input
    129 
    130 ```
    131 3
    132 
    133 6 3
    134 
    135 5 5 4 5 2 2
    136 
    137 3 4 5
    138 
    139 2 2 5
    140 
    141 1 5
    142 
    143 3 4 1 6
    144 
    145 4 2 6 1 5
    146 
    147 0
    148 
    149 0
    150 
    151 6 2
    152 
    153 1 4 4 1 5 2
    154 
    155 3 6
    156 
    157 4 6 3 4 5
    158 
    159 4 6 5 3 4
    160 
    161 0
    162 
    163 1 5
    164 
    165 1 6
    166 
    167 0
    168 
    169 2 1
    170 
    171 4 3
    172 
    173 1
    174 
    175 0
    176 
    177 1 1
    178 ```
    179 
    180 Output
    181 
    182 ```
    183 0 0 0 0 0 2 
    184 0 0 0 0 0 0 
    185 0 0
    186 ```
    187 
    188 Note
    189 
    190 In the first test case of the first sample, it is optimal:
    191 
    192 * Get a potion of the first type by buying and mixing $2$, $4$ and $5$;
    193 * a potion of the second type can only be obtained by purchasing it;
    194 * Nastya already has an unlimited number of potions of the third type;
    195 * a potion of the fourth type is more profitable to buy than to buy and mix other potions;
    196 * a potion of the fifth type can only be obtained by purchasing it.