Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

hamidreza.hanify's blog

Is it possible to solve Xor-MST using prim's algorithm?
By hamidreza.hanify, history, 6 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

»
6 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(n2) time which still will be slow.

→ Reply
  • »
    »
    6 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?

    → Reply
»
6 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

→ Reply