Hello codeforces,
I'v recently been struggling with this problem Xor-MST.In it's tutorial it says u should use Boruvka's algorithm. For sake of learning i'v been trying to solve it using prim's algorithm but it runs out of time. I was wondering if it's some inefficiency in my coding or it's the algorithm which can't solve the problem in given time? here is my last code submitted: MY CODE
thanks in advance.
Your solution has complexity
which is slow. Prim can be implemented in O(n2) time which still will be slow.
so does it means this algorithm can't handle it in under 2sec time limit cause it's slow anyway?
I think you can use Prim's algorithm with priority queue and trie structure to AC. The time complexity should be n.log(n) multiply a constant. Here is a code from my friend who used Prim's algorithm and trie structure :) CODE