Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

A code that magically passes Div 812 E Cross Swapping but don't know why

Revision en2, by Ivan_len, 2022-08-07 18:46:19

Here is the link to the submission: 167414309

Basically, I created a copy of each n swapping position (so that there are 2*n nodes in the dsu), and I tried to merge from the entry of the matrix with the highest priority. However, then when I want to swap according to the result of the blocks in the dsu, this code magically passes and I don't know why (because it may happen that all root of blocks are nodes <n). It seems the correctness is dependent on the order of nodes that I pass into the dsu merge function. Can anyone tell me why is this correct/wrong on some test cases?


  Rev. Lang. By When Δ Comment
en2 English Ivan_len 2022-08-07 18:46:19 0 (published)
en1 English Ivan_len 2022-08-07 18:45:57 715 Initial revision (saved to drafts)