What is the error in the first logic? Related to Edu119 Problem E

Revision en2, by the_drunken_knight, 2021-12-19 12:15:29

Problem: https://codeforces.me/contest/1620/problem/E

I was trying to apply some dsu-like logic in Problem E, when they asked for replacement of every $$$x$$$ with $$$y$$$ in the array, but it gave me WA on test 4.

The idea which I used during the contest:

from = replacement[x], to = replacement[y]
while(replacement[to] != to) to = replacement[to];
replacement[from] = to;

And, the idea which gave AC after the contest,

replacement[x] = replacement[y]

I know that the latter one is clever and more sleek, but why the former one fails? Can anyone please suggest a counter-case for it?

Except for these idea, the rest of code was exact same!

Submission 1 (with first logic): https://codeforces.me/contest/1620/submission/139872871
Submission 2 (with second logic): https://codeforces.me/contest/1620/submission/139872969

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English the_drunken_knight 2021-12-19 12:15:29 195 Tiny change: '39872871\nSubmissi' -> '39872871\n\nSubmissi'
en1 English the_drunken_knight 2021-12-18 21:46:32 738 Initial revision (published)