light42's blog

Need help for this disjoint set problem.
By light42, history, 9 years ago, In English

Click here for the problem

At first sight, it seems that it can simply be solved using disjoint set ds. But the problem is more complicated because we handle two kinds of sets at once. Can anyone give a hint for this problem? (PS : I've already try to write and proof my solution for 3 days but still get WA. I suspect I didn't cover all the possible cases in the problem. And sorry if I'm not explaining my solution. It's too messed up I don't want to use it anymore.)

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Hint: you can use a single DSU but maintain additional information about vertices.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we do a valid setEnemies procedure, what we must do so the result will truly represent the current relationships between those sets? I'm really confused because the rule for enemy relationship is different than friend relationship.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      The rules are simply saying that people from the same country are friends, and people from different countries are enemies.

      → Reply