[ Debug Help] [Spoj] ADABRANC - Ada and Branches

general
,
1

I am getting a SIGSEGV error, i am unable to find where my code might be accessing invalid memory location.

[UPDATE]

Got Accepted, instead of passing comparator for sorting, i passed greater<vector<int>>().

Can anyone explain why external comparator function gave SIGSEGV and greater<vector<int>>() did not?

Problem Link

#include <bits/stdc++.h>
using namespace std;

struct node{
    int par;
    int count;
    int rank;
};

bool comp(vector<int> &a, vector<int> &b){
    return a[0] >= b[0];
}

node find(vector<node> &parent, int a){
    while(parent[a].par != a){
        a  = parent[a].par;
    }
    return parent[a];
}

void unionSet(int a, int b, vector<node> &parent){
    node aRoot = find(parent, a);
    node bRoot = find(parent, b);

    if(aRoot.par == bRoot.par)return;

    if(aRoot.rank > bRoot.rank){
        swap(aRoot, bRoot);
    }

    parent[aRoot.par].par = bRoot.par;

    parent[bRoot.par].count += aRoot.count;

    if(aRoot.rank == bRoot.rank){
        parent[bRoot.par].rank += 1;
    }
}

void solve(){
    int n, m, q;
    cin>>n>>m>>q;
    
    vector<node> parent(n);

    for(int i=0;i<n;i++){
        parent[i].par = i;
        parent[i].rank = 0;
        parent[i].count = 1;
    }

    vector<vector<int>> edges(m, vector<int>(3)), queries(q, vector<int>(2));

    for(int i=0;i<m;i++){
        cin>>edges[i][1]>>edges[i][2]>>edges[i][0]; //w,a,b
    }


    for(int i=0;i<q;i++){
        cin>>queries[i][1]>>queries[i][0]; // w, src, index
        queries[i].push_back(i);
    }


    sort(edges.begin(), edges.end(), comp);
    sort(queries.begin(), queries.end(), comp);

   // debug2d(edges);

    vector<int> res(q);
    int j = 0;

    for(int i=0;i<q;i++){
        while(j < m && edges[j][0] >= queries[i][0]){
            unionSet(edges[j][1], edges[j][2], parent);
            j++;
        }
        res[queries[i][2]] = find(parent, queries[i][1]).count;
    }

    for(int i=0;i<q;i++)cout<<res[i]<<endl;

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
    int t;
    t = 1;
    while(t--){
    	solve();
    }
    return 0;
}
2
Debug output 
suman@skynet:~/temp$ c++ -g Wrong.cpp 
suman@skynet:~/temp$ gdb a.out 
GNU gdb (Ubuntu 9.2-0ubuntu1~20.04) 9.2
Copyright (C) 2020 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from a.out...
(gdb) run < in.in > output.out 
Starting program: /home/suman/temp/a.out < in.in > output.out

Program received signal SIGSEGV, Segmentation fault.
comp (a=std::vector of length 0, capacity 0, b=std::vector of length 3, capacity 4 = {...}) at Wrong.cpp:11
11          return a[0] >= b[0];
(gdb) quit
A debugging session is active.

        Inferior 1 [process 216994] will be killed.

Quit anyway? (y or n) y
suman@skynet:~/temp$

Focus on this:

Program received signal SIGSEGV, Segmentation fault.
comp (a=std::vector of length 0, capacity 0, b=std::vector of length 3, capacity 4 = {...}) at Wrong.cpp:11
11          return a[0] >= b[0];

It says vector of length 0, but you are trying to access the element at index 0, hence the segmentation fault.

3

What’s the testcase?

4

It is randomly generated. I am pasting the generator here. If you need the actual test case which I used, comment about it and I will upload it to my git.

Test case generator - Python code 
from random import randint

with open("in.in", "w") as file:
    file.write("100000 200000 300000\n")
    taken = set()
    for i in range(2 * 10**5):
        a, b = 0, 1
        while (a, b) in taken:
            a = randint(0, 10**5 - 1)
            b = randint(0, 10**5 - 1)
            while b == a:
                b = randint(0, 10**5 - 1)
        taken.add((a, b))
        file.write(str(a) + " " + str(b) + "\n")
    for i in range(3 * 10**5):
        a = randint(0, 10**5 - 1)
        y = randint(1, 10**5)
        file.write(str(a) + " " + str(y) + '\n')