Why does using unordered_set.clear() lead to a TLE?

Revision en1, by iamsr, 2019-05-15 21:11:32

In problem 1167C, this submission gets a TLE. However, changing the line ele.clear(); to ele = unordered_set<lli>(); gets an AC. Why does that happen? I read the docs and std::unordered_set::clear has complexity "linear in the size of the container, i.e., the number of elements". We know that the container ele's size won't exceed n, the total number of elements. Thus, the total cost of clear operations does not exceed n. So, it just adds an extra complexity of n to my original code. At max, my code execution time should double, however, my AC code takes 499ms, so the code with .clear() shouldn't have taken more than around 1sec in any circumstances.

Could anyone help me understand the problem here?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English iamsr 2019-05-15 21:11:32 1017 Initial revision (published)