Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

Правка en2, от 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. Язык Кто Когда Δ Комментарий
en2 Английский Ivan_len 2022-08-07 18:46:19 0 (published)
en1 Английский Ivan_len 2022-08-07 18:45:57 715 Initial revision (saved to drafts)