Woah, didn't know that, that's some crazy amount of time difference man. The vector solution is taking around 8000ms whereas pair one is running at around 250ms

If you know that your vectors are going to be of specific size, use std::array instead. So, the compiler knows beforehand how much memory to allocate. And, this can help improve run time. To be able to use std::array like vectors (syntactically) you could use typedef maybe, something like:

typedef array<int, 2> vect; // Name according to your likeness

void func(vect & a, vect & b) {
 // do your stuff
}
vect a = {2, 3};

// etc.

$$${std::pair<T1, T2>}$$$ is faster than $$${std::vector<T>}$$$ with size $$$2$$$ the reason behind this is vectors are dynamic in nature (size can be modified) where as pairs are static such as array. You may read here as well!

PS: You may use $$${std::array<T, size>}$$$ or $$${std::tuple<T1, T2...>}$$$ as well.

amortised analysis

Yes, I also faced a similar problem,

Question: https://www.geeksforgeeks.org/problems/minimum-edges/1?utm_source=geeksforgeeks&utm_medium=ml_article_practice_tab&utm_campaign=article_practice_tab

When i used vector<vector> adj[n+1], I got TLE where as vector<pair<int,int>> adj[n + 1] works fine.

At first I thought this was due to the better indexing of your dp array (thanks to cache optimisations).

But it turns out that my modified versions are still getting TLE. Fortunately, I think I understand what is going on. It is indeed because of cache optimisations. When you have a vector of pairs, the access to the pairs is very fast because they are contiguous in memory : it's easy to keep them in high speed caches. Whereas, if they are far apart, they will lie in different memory pages, so it is going to require much more time to access.