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; }
Dude, u not deserve yellow color with such obvious questions.
Dude, you don't deserve purple if you don't know about new year magic.
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.
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.
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:
The result: 189085171
Hello I am a very beautiful girl
Here's one (probably bad) way to replicate what the recursive code is doing iteratively: https://codeforces.me/contest/1559/submission/189085433
In your submissions, iterative isn't updating the f[id][x] at all. So if you make another query with the same arguments, it will run the same loop again. In recursive one, the loop will run only the first time.