prakhar_111's blog

Help in a Div3 question
By prakhar_111, 5 years ago, In English

Hello, I was trying to solve this question. I am getting TLE on test 8. What I did is first, I stored the pairs which quarrel in an adjacency list like we store in the graph. Then I sorted the programmers based on their skills in increasing order. Then I iterated one by one from the smallest skill person to the highest skilled programmer and kept storing their skills in multiset. So to find the answer for each, I subtracted the adj[x].size() and the same skilled programmers that have occurred before. I can't understand why I am getting TLE. Can someone please explain the reason? Also, what should I incorporate into my code to solve this problem? I find my approach similar to the tutorial. My submission. I also try to use unordered multiset instead but that too is giving TLE. Link

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

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

From cpp reference: the complexity of multiset::count is Logarithmic in the size of the container plus linear in the number of the elements found. Use map instead

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

73553095 You Can Look My Submission.

→ Reply