Ivan_len's blog

By Ivan_len, history, 19 months ago, In English

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?

Full text and comments »

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