I was trying to submit this -> Remove Max Number of Edges to Keep Graph Fully Traversable question.
but I got TLE because of sort using rbegin
sort( edges.rbegin(), edges.rend())
but after change with comparator funtction code got accepted.
sort(edges.begin(), edges.end(), [&](vector <int> &a, vector <int> &b){
return a[0] > b[0];
});
I tried to run this in local and got similar performance but when I used some different build command I got 2x time difference for $$$N = 10^5$$$
Build command:
g++ a.cpp
g++ -std=c++17 -Wshadow -Wall -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -DLOCAL a.cpp
output using 1st build command:
0.0290290006s
0.0652360022s
output using 2nd build command:
0.9816750288s
2.1033749580s
Following code I used for bench-marking.
Can anyone explain why this time difference happening?
Will this happen in code-forces also?
same thing happened to me last month..... was using sort(vector.rbegin(),vector.rend()) and got tle.....after the contest i used sort(vector.begin(),vector.end(),greater()) and then got AC... i used to thought that complexity of both sorting is same
It is happening because you have used the compile flags without knowing what they do.
-D_GLIBCXX_DEBUG
: it inserts some debug / sanity checks that can really slow your code down. For example, you may get $$$O(n)$$$ complexity forstd::binary_serach
.And you forgot the most important flag
-O2
. With-O2
both of them takes same time.That's why I prefer using comparators