TLE because of sort using rbegin

Правка en2, от abba5, 2020-10-21 12:34:00

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];
        });

Submission Using rbegin

class Solution {
    
public:
    
    vector <int> d1;
    vector <int> d2;

    vector <int> s1;
    vector <int> s2;

    
    int parent(int x, vector <int> &dsu){
        if(x == dsu[x]){
            return x;
        }else{
            dsu[x] = parent(dsu[x], dsu);
        }
        
        return dsu[x];
    }
    
    int add(int a, int b, vector <int> &dsu, vector <int> &s){
        int p1 = parent(a, dsu);
        int p2 = parent(b, dsu);
        if(p1 == p2){
            return 1;
        }else{
            dsu[p1] = p2;
            s[p2] += s[p1];
            return 0;
        }
    }
    
    
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        
        d1 = vector <int> (n+1, 0);
        d2 = vector <int> (n+1, 0);
        
        s1= vector <int>(n+1, 1);
        s2 = vector <int> (n+1, 1);
        
        for(int i =0 ; i <= n; ++i){
            d1[i] = i;
            d2[i] = i;
        }
        
        sort(edges.rbegin(), edges.rend());
        
        int ans = 0;
        
        for(auto &data: edges){
            if(data[0] == 3){
                ans += add(data[1], data[2], d1, s1);
                add(data[1], data[2], d2, s2);
            }else if(data[0] == 2){
                ans += add(data[1], data[2], d1, s1);
            }else if(data[0] == 1){
                ans += add(data[1], data[2], d2, s2);
            }
        }
     
        
        if(s1[parent(1, d1)] == n and s2[parent(1, d2)] == n){
            return ans;
        }else{
            return -1;
        }
        
    }
};

Submission Using comparator

class Solution {
    
public:
    
    vector <int> d1;
    vector <int> d2;

    vector <int> s1;
    vector <int> s2;

    
    int parent(int x, vector <int> &dsu){
        if(x == dsu[x]){
            return x;
        }else{
            dsu[x] = parent(dsu[x], dsu);
        }
        
        return dsu[x];
    }
    
    int add(int a, int b, vector <int> &dsu, vector <int> &s){
        int p1 = parent(a, dsu);
        int p2 = parent(b, dsu);
        if(p1 == p2){
            return 1;
        }else{
            dsu[p1] = p2;
            s[p2] += s[p1];
            return 0;
        }
    }
    
    
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        
        d1 = vector <int> (n+1, 0);
        d2 = vector <int> (n+1, 0);
        
        s1= vector <int>(n+1, 1);
        s2 = vector <int> (n+1, 1);
        
        for(int i =0 ; i <= n; ++i){
            d1[i] = i;
            d2[i] = i;
        }
        
         sort(edges.begin(), edges.end(), [&](vector <int> &a, vector <int> &b){
            return a[0] > b[0];
        });
        
        
        int ans = 0;
        
        for(auto &data: edges){
            if(data[0] == 3){
                ans += add(data[1], data[2], d1, s1);
                add(data[1], data[2], d2, s2);
            }else if(data[0] == 2){
                ans += add(data[1], data[2], d1, s1);
            }else if(data[0] == 1){
                ans += add(data[1], data[2], d2, s2);
            }
        }
     
        
        if(s1[parent(1, d1)] == n and s2[parent(1, d2)] == n){
            return ans;
        }else{
            return -1;
        }
        
    }
};

I tried to run this in local and got similar perfomance but when I used some different build command I got 2x tiime difference.

Build command:

g++ a.cpp

g++ -std=c++17 -Wshadow -Wall -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -DLOCAL a.cpp

Following code I used for benchmarking.

Benchmarking code

int n;
cin >> n;
srand(time(0)); 
vector <int> ans(n);

for(int i = 0; i < n; ++i){
	ans[i] = random() % 100000;
}



vector <int> xyz = ans;

const clock_t begin_time = clock();

sort(ans.begin(), ans.end(), greater <int> ());

std::cout << float( clock () - begin_time ) /  CLOCKS_PER_SEC << endl;

const clock_t begin_time2 = clock();
sort(xyz.rbegin(), xyz.rend());

std::cout << float( clock () - begin_time2 ) /  CLOCKS_PER_SEC << endl;

I think that leetcode is using similar build command to execute the program. Can anyone explain why this time difference happening?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский abba5 2020-10-21 13:45:49 187 Tiny change: 'difference. for N = 10^5\n\nBuild ' -> 'difference for $N = 10^5$\n\nBuild '
en9 Английский abba5 2020-10-21 13:10:49 7 Tiny change: 'ppening?\nWill this happened in code-f' -> 'ppening?\n\nWill this happen in code-f' (published)
en8 Английский abba5 2020-10-21 12:51:15 8 Tiny change: '//p.ip.fi/e8Pf)\n\nCan a' -> '//p.ip.fi/Wmnz)\n\nCan a'
en7 Английский abba5 2020-10-21 12:47:17 25 Tiny change: '(https://pastebin.com/ct1QGJZM)\n\n[Subm' -> '(https://p.ip.fi/wuD8)\n\n[Subm'
en6 Английский abba5 2020-10-21 12:46:02 12 Tiny change: 'ommand: \n```g++ a.cpp```\n\n\n```g' -> 'ommand: \n\n\n```g++ a.cpp```\n\n\n\n```g'
en5 Английский abba5 2020-10-21 12:42:38 651
en4 Английский abba5 2020-10-21 12:40:10 36
en3 Английский abba5 2020-10-21 12:39:11 3486
en2 Английский abba5 2020-10-21 12:34:00 16
en1 Английский abba5 2020-10-21 12:30:36 5080 Initial revision (saved to drafts)