K0DEL's blog

recursice vs iterative
By K0DEL, history, 23 months ago, In English

I was trying to solve this problem: 1559D1 - Mocha and Diana (Easy Version)

I used the editorial solution for this and just made a small change instead of recursively finding the parent of the node I used an iterative way and it took a lot of time and I want to know why this is happening. The recursive way took 15ms while the iterative way took 764ms.

The editorial submission with recursive method: 189082733 The same submission with iterative method: 189082883

The only difference between the 2 submissions is "getf()" function.

for the recursive approach: int getf(int id, int x){return x == f[id][x] ? x : f[id][x] = getf(id, f[id][x]);}

for the iterative approach: int getf(int id, int x) { while (x != f[id][x]) x = f[id][x]; return x; }

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
23 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Dude, u not deserve yellow color with such obvious questions.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    Dude, you don't deserve purple if you don't know about new year magic.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      Before writing that comment I looked at his rating first. And I mean that he shouldn't disgrace yellow color and should change it to some another.

      So I know about NY magic, don't make fast conclusions.

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        LMAO. Okay, how are they disgracing yellow color here? It is allowed by CF to do it. Do you want to say everyone who's using new year magic to show higher color disgracing it?

        Also, did you also find out OP's preferred pronouns somewhere? Please do follow your own advice about making fast conclusions.

        → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You use path compression like in DSU in the recursive approach, where as in the second approach you don't compress paths at all. I.e. if you want to get equavilent solution you should have written the following:

return x == f[id][x] ? x : getf(id, f[id][x]);

The result: 189085171

→ Reply