hamidreza.hanify's blog

By hamidreza.hanify, history, 3 years ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • -19
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Your solution has complexity which is slow. Prim can be implemented in O(n 2) time which still will be slow.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    so does it means this algorithm can't handle it in under 2sec time limit cause it's slow anyway?

»
3 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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