Srikant VS Terrorists

Joyeeta.28 CodeSpark 2021
Limits 1s, 512 MB

Srikant is an agent in an Intelligence agency. He is now heading a secret mission against a group of terrorists. His colleague, JK has been taken hostage by the terrorists. They are determined to kill JK on kk-th minute. There are nn cells (which are more like dungeons) numbered from 11 to nn in the territory of the terrorists.

Srikant had taken a road map of these cells with him while leaving for his mission but lost it before he reached there. He is standing at the first cell. He had tried to memorize the road map before he lost it. But his memory is not very sharp. He only remembers one road or none for each cell. The road he remembers for cell ii leads to cell aia_i. If he cannot remember any road for a cell, it will be denoted by 00. The time required to move from one cell to the other is exactly 11 minute.

The number of mm terrorists are guarding one or more cells. Srikant must kill all the terrorists within kk minutes to save his colleague.

To move from a cell, Srikant needs to kill all the terrorists guarding the cell if there are any. Else he will get killed. Time after killing all the terrorists doesn’t count because JK will already be safe by then as nobody would be there to harm him. If Srikant reaches a cell to kill a terrorist on the kk-th minute, he cannot save JK because on that very minute the terrorist will shoot JK and kill him.

Srikant has rr rounds of bullets in his possession (each round consists of 66 bullets). Srikant must shoot each of the terrorists a number of times in order to break his shield, disarm him and finally kill him. This number may vary from one terrorist to the other. If the required bullets to kill a terrorist are greater than the number of bullets Srikant is left with, he cannot kill the terrorist and the terrorist shoots him back. For the convenience of calculation, the time required to kill a terrorist or to reload the gun is not taken into consideration.


[N.B: The number of times a terrorist needs to be shot is equivalent to the number of bullets needed to kill him.]


The first line contains five space-separated integers n,mn,m(1n,m106)(1 \le n,m \le 10^6), kk (1k109){(1 \le k \le 10^9)}, rr(1r109)(1 \le r \le 10^9) - that denote the number of cells, total number of terrorists, the minute on which JK will be killed and the number of rounds of bullets.

The second line contains nn space-separated integers a1,a2,,ai,,ana_1,a_2, \dots, a_i, \dots, a_n (0ain)(0 \le a_i \le n) that describe the cell numbers Srikant can move to.

Next mm lines contain two space-separated integers xx (1xn)(1 \le x \le n) and yy (1y109)(1\le y \le10^9) that denote the cell number the jj-th (1jm){(1 \le j \le m)} terrorist guards and the number of times he needs to be shot.


Print “Yes” if Srikant can save his colleague, otherwise print “No” (without quotes). You can print each letter in any case. For example, “YeS”, ”YES”, “yES”, “no”, ”NO” etc. are also acceptable.


6 4 6 3
6 4 2 0 3 5
2 3
3 5
5 4
6 5
5 3 3 3
5 4 0 0 2
1 18
2 4
2 2


Login to submit.


80% Solution Ratio
faria_efaEarliest, Jul '21
prodip_bsmrstuFastest, 0.1s
prodip_bsmrstuLightest, 12 MB
antihashShortest, 824B
Toph uses cookies. By continuing you agree to our Cookie Policy.