Gates to Another World solution codeforces
William wants to test you and see how you can handle processing the following queries in this game universe:
- Destroy planets with numbers from to inclusively. These planets cannot be moved to anymore.
- Figure out if it is possible to reach planet from planet using some number of planetary gates. It is guaranteed that the planets and are not destroyed.
Input Gates to Another World solution codeforces
The first line contains two integers, ( , ), which are the number of bits in binary representation of each planets’ designation and the number of queries, respectively.
Each of the nextlines contains a query of two types:
block l r — query for destruction of planets with numbers from to inclusively ( ). It’s guaranteed that no planet will be destroyed twice.
ask a b — query for reachability between planets and ( ). It’s guaranteed that planets and hasn’t been destroyed yet.
Output Gates to Another World solution codeforces
For each query of type ask you must output “1” in a new line, if it is possible to reach planet from planet and “0” otherwise (without quotation marks).
3 3 ask 0 7 block 3 6 ask 0 7
Copy Gates to Another World solution codeforces
6 10 block 12 26 ask 44 63 block 32 46 ask 1 54 block 27 30 ask 10 31 ask 11 31 ask 49 31 block 31 31 ask 2 51
output Gates to Another World solution codeforces
1 1 0 0 1 0
The first example test can be visualized in the following way:
Next after query block 3 6 the graph will look the following way (destroyed vertices are highlighted):
As mentioned previously William really likes playing video games. In one of his favorite games, the player character is in a universe where every planet is designated by a binary number from 00 to 2n−12n−1. On each planet, there are gates that allow the player to move from planet ii to planet jj if the binary representations of ii and jj differ in exactly one bit.