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.
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.
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
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
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):