I believe that your solution (as well as the solution of mrho) are actually unintended and run in quadratic on an edge case, which you barely passed through constant factor tricks. Note that the Java submission of uwi runs in 0.24 seconds.
I also passed with O((n*2^k+e)*log(n*2^k)) but I think this theoretical complexity isn’t actually achievable. I cant think of a case where all bitmasks are actually traversed + are all “valuable” (since we just break out of dijkstra once we find the first path).
The intended solution was to compress the graph to just keys and locked nodes using O(K) Dijkstra, and then to run the subtask 2 solution on that graph. I think that the theoretical complexity is achievable (consider all keys connected to each other and connected to the node 1) but unfortunately did not have a specific test case. It seems that most people who tried n*2^k failed subtask 3, regardless.
I apologise, it seems that your solution doesn’t encounter the O(N^2) blowup that I thought it did. (I guess mrho’s solution would also be same?) Unfortunately, I don’t think I have the permissions to check the cerr from the file. Testing it locally finds that it is pretty much O(N).
Apologies for the tight TL. Solutions of testers and setter were double as fast because they used map with key as int, I believe (which also led to the possibility of O(N^2) blowup). Congrats on all AC in contest, though.
P.S. i have put asserts in the code at every place after i take input assert(y!=-1). but i am not getting runtime error which means all my asserts are passing. but still i am getting WA.
Thanks 