array of vector is faster than vector of vector for storing adjaceny list?
Difference between en1 and en2, changed 158 character(s)
Hi all, I recently came across an issue that I am  unable to comprehend. While solving problem 1337C, I used the same code twice except using a `vector<vector<int> > adj(n)` in [submission:83595937] and `vector<int> a[n]` in [submission:83693762]. For some reason, the first submission timed out and the second one passed. I thought maybe it has something to do with the fact that vectors aren't preallocating the proper space but that shouldn't be the case as I am mentioning the size `n` while declaring the vector of vector as well. I searched for this problem on the internet but the discussion is almost always about vector vs arrays and not 2D containers. Thanks for the help!

EDIT: it's solved! Thanks to [user:vip_in_hunt_for_code,2020-06-15] for pointing it out. Passing vvi as reference fixed the problem: [submission:83860879]

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English diradon 2020-06-15 19:32:50 158
en1 English diradon 2020-06-15 19:13:58 756 Initial revision (published)