The XORMIN problem from April’s Long Challenge.
This is the logic that I implemented:-
- Find the euler tour and create the array (ar)
- Find starting and ending time of each index(array ‘tme’ of pairs)
- Each trie stores its children, minimumVertex and maxStartTime.
- trie[i] stores values from 1 upto i in ar.
- Create trie[i+1] from trie[i] using persistence
- For a query (vertex, k) find the max xor in the trie[ tme[vertex].second ] using the help of maxStartTime.
Is this logic wrong? If not then what could be the possible reason for RE in some test cases?
Here is the code link .
PS: The code is not difficult to understand-it is commented.