vatayush's blog

CF Round #151 Div2 D
By vatayush, 9 years ago, In English

hi!i was solving this problem.it's strange that this submission1 got TLE while when i used set instead of visited array to keep track of colors the same code got AC.My AC code.Can someone please explain me why??

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Each time when you create an array it takes O(size) time. So your algorithm in worst case will create 100000 elements array 100000 times what is too much. If you create set it is empty so it takes O(1) time and O(log n) for each operation.

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

    thanks so much...i didn't know about this :)

    → Reply