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

Parity @ Timus Online Judge — Time Limit Exceeding ?
Автор lostbrain, 10 лет назад, По-английски

Hello everyone, I was trying this problem for some days.The idea was kind of simple.If the pair (x,y) has even parity then pair (0,x-1) and pair(0,y) will have same parity.If the pair(x,y) has odd parity then pair (0,x-1) and pair(0,y) will have different parity.I modeled the pairs to a graph.I defined two pairs to be adjacent if they have same parity.Then I used Depth First Search to spot any contradiction in the graph.I am certain that the algorithm is correct(Hopefully :P) but i am not sure why i am getting a Time Limit exceeding verdict.Is there a better idea or implementation to this problem ?? Please help me out. Here is my code

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

I havent solved it , but if its the problem with TLE , then i can suggest an improvement . Instead of dfs use union_find aka disjoint_set_union. This should get the computation within time limit

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

Thank you moinul.shaon.Your idea helped me get a AC.Here is my final AC code.Can anyone explain how DSU was passing the tests and DFS did not ?

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

    Before you were doing dfs after every query . So solution order O(q * (V+E) ) . After union_find O( q*log(V) ) .

    Union find is a good data structure to add edge in a graph and checking their connectivity . U needed just that

    → Ответить