lazy_dumbo's blog

By lazy_dumbo, history, 5 weeks ago, In English,
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Please, do not do s|=(1<<(x)); with long long values, use s|=(1ll<<(x));

As far as I understood the problem you need bucket sort for highest setted bit. Then you can ask yourself whether you can construct the connected graph not using the roads with highest cost token (with id $$$k-1$$$) or not (ala MST by means of DSU). If so you can exclude this token from the final list. And then you can try to construct connected graph not using the roads with token id $$$k-2$$$. And so on. Finally you will have the list of not used tokens. The complexity is $$$O(k*m*DSUfactor)$$$, where $$$DSUfactor$$$ is $$$log(n)$$$ for your DSU implementation.

Code

UPD: added code and fixed some errors.