dg25's blog

By dg25, history, 2 months ago, In English

Is there any massive time complexity difference between erasing a value from the set using -- set_name.erase(iterator) and set_name.erase(set_name.find(iterator)) when we are sure that iterator refers to a value present in the set..i am asking this because this shows time limit exceeded but this one does not shows any time limit exceeded ...please help

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dg25 (previous revision, new revision, compare).

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

set.erase(iterator) is O(1) while set.erase(value) is O(log set.size())

set.erase(value) == set.erase(set.find(value))

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

In your first submission(TLE) you are not using the multiset::erase(iterator) version but instead using the multiset::erase(val). Since you have derefernced the reverse iterator auto it = *values.rbegin();, it stores the value at the end of the multiset.

According to C++ Reference, the complexity of

  1. multiset::erase(iterator) -> constant

  2. multiset::erase(val) -> logarithmic in container size, plus linear in the number of elements removed.

Since the second version removes every occurence of the value(if present) present in the multiset.

And if you need to remove only 1 occurence of the multiple then you should use multiset::find(val) to get a iterator and then remove using the 1st version.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Bro, you're just copying map<int, ll> every time in dfs, it's pretty heavy, you know.