Why is vector<vector> much slower than static int array in my binary lifting implementation.

Revision en4, by Argentum47, 2025-11-19 18:15:49

I was solving the Planets Queries I problem in CSES (a standard binary lifting problem).

After getting a few TLE on one of the test cases, I finally got AC, but it took 1.00 seconds to pass that test case, which is way too close. On checking other submissions with exact same logic, and investigating a bit more, I changed vector<vector> declaration in my code to static int array declaration, and my code, with everything being exact same, worked in 0.60 seconds.

Usually there shouldn't be such a drastic difference. While solving codeforces problem, I have observed that vectors and static array take the same time, and sometimes vectors are faster.

Can anyone explain the reason behind this? Thanks.

Submission using vector<vector> : https://cses.fi/paste/7d2b7a0b66df52a2ea28b6/

Submission using static int array : https://cses.fi/paste/6d8b9ef1a192caa1ea28f1/

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English Argentum47 2025-11-20 11:43:07 3 Tiny change: 'ntation, I did vec' -> 'ntation, If I did vec'
en9 English Argentum47 2025-11-19 19:16:56 1017
en8 English Argentum47 2025-11-19 18:20:07 0 (published)
en7 English Argentum47 2025-11-19 18:19:40 2
en6 English Argentum47 2025-11-19 18:19:03 21 Tiny change: 'ged vector<vector<int>> declarat' -> 'ged vector\<vector\<int\>\> declarat'
en5 English Argentum47 2025-11-19 18:17:53 4 Tiny change: 'hanks.\n\nSubmissi' -> 'hanks.\n\n<int>\nSubmissi'
en4 English Argentum47 2025-11-19 18:15:49 14 Tiny change: 'econds. \nUsually ' -> 'econds. \n\nUsually '
en3 English Argentum47 2025-11-19 18:14:12 1 Tiny change: 'ea28b6/ \nSubmissi' -> 'ea28b6/ \n\nSubmissi'
en2 English Argentum47 2025-11-19 18:13:19 16
en1 English Argentum47 2025-11-19 18:12:48 986 Initial revision (saved to drafts)