Блог пользователя codeDominus

Require help for spoj question BTCODE_G
Автор codeDominus, история, 8 лет назад, По-английски

LINK for the problem I am learning DSU and came up with this question but could not apply DSU. It will be of great help if someone tell the logic for solving this problem.

UPD 1 :solved the question LINK for answer

Теги dsu
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Good day to you!

Firstly, set all colors to "UNDEF" [for example -1] {uncolored} and build graph (for example with vectors [I assume you can do this, if not, ask more!]).

Now for each query of type 1, set color to "y" and iterate over all "neighbors" and check whether their color is same — in case of "yes", connect them with DSU.

The second query just ask if their DSU-component is same.

Since "he colors each node at most once" there is no problem with "erasing connections" (even though it would be solvable too, just much harder).

Good Luck!

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Thanks

    solved the question.

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Hi ! Sorry if I'm late, but can you tell me how do you solve it without that condition "he colors each node at most once" ?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hmm I got some doubts about it, because it is true that graph of "star-shape" with queries to the star (which means simple iteration over neighbors would time out) will "kill" it, but if it will be "reasonable" graph, then Link-Cut-Tree shall do it (instead of DSU).

      → Ответить