K.Outis's blog

By K.Outis, history, 10 days ago, In English

If anyone can help me solve this code bug 300498718 , I would be grateful 160D - Edges in MST.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Hi, here are some problems i found in your code.

Theory :

  1. after adding edges with weight i, you run only 1 dfs but there might be more than 1 connected component so you have to run it for each connected component made by these new edges

  2. explained at the end

Implementation :

  1. initial value of mn should be 1e6

  2. vector ver has to be cleared after every weight i or else there can be a O(mn) running time

  3. assigning h[v] = 0 at the end of dfs is risky, i think there should be a test case that it will make your code detect false bridges

after correcting above mistakes you will arive at the main issue and that is the running time because you keep all the previous edges and continue to add new edges so running DFSs for weight i wont be efficient and result in m*(m+n) running time TLE :(

It's better to somehow compress your connected components after adding edges with weight i so you wont go over repeating edges in the future weights

I hope you continue to push forward in CP. send my regards to ParsaDox

  • »
    »
    9 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you so much for taking the time to share this with me. I've been following your videos on "تک شاخ" and I have to commend you for your efforts in providing educational justice. So this code seems to be problematic in many ways.

    To be honest, I don't have easy access to ParsaDox. Maybe because I don't go to Farz1 and things are a little more complicated.

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I hope your next code for this problem be a first try accepted. And about Parsa i saw his name in your previous blog so i thought maybe he is your coach. anyway have a good day and dont stop working hard till you get your gold