The Great Escape: Runtime Error

I tried solving The Great Escape on the INOI server: http://opc.iarcs.org.in/index.php/problems/GREATESC

I used a simple BFS to find the minimum number of jumps. But my code is showing segmentation fault in the last test case. Can anyone one point out my mistake?
My code:

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

vector<int> adjlist[3500];
queue<int> bfs;

int main()
{
    int n,m;
    cin >> n >> m;
    int a,b;
    while(m--)
    {
        cin >> a >> b;
        a--; b--;
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }
    int s,t;
    cin >> s >> t;
    s--;
    t--;
    int v[n];
    memset(v,-1,sizeof(v));
    v[s] = 0;
    bfs.push(s);
    while(!bfs.empty())
    {
        int node = bfs.front();
        bfs.pop();
        int d = v[node];
        for(unsigned int i = 0;i < adjlist[node].size();i++)
        {
            int node2 = adjlist[node][i];
            if(v[node2] == -1)
            {
                v[node2] = d+1;
                bfs.push(node2);
            }
        }
    }
    if(v[t] == -1) cout << 0 << endl;
    else cout << v[t] << endl;
    return 0;
}

It might be a problem with the testdata, but maybe not. I have the same issue.

But many people have got 100 :-/

I have the same problem too!

They would’ve looked at the test cases I suppose. A lot of number of iarcs problems seem to have issues

I asked someone. The test data is faulty. Just check if m = 641902. If it is then output 0 and exit (although the correct answer is 2800). For other m, run the normal program.

Yeah, as I said the test cases must be faulty. IMO it’s not of any use to do these kind of modifications, you don’t learn anything, just get some points in IARCS site which is of no purpose.

@superty Are the test cases faulty for DEVIOUS as well? I am getting only 80 points.

I got 80 as well.
In future you can check in my profile: http://opc.iarcs.org.in/index.php/users/Superty

Hello @ketanhwr, I am also having the same problem as you in GREATESC. I used the same logic as yours. I once asked Prof. Madhavan Mukund about what can be the probable causes for “SEGMENTATION FAULT”. He replied that perhaps I am accessing an illegal memory. However, I recently can to know that it may be shown because of crossing the memory limits. Therefore, though adjacency list representation uses O(n+m) memory, it might be crossing the memory limits (though I am not sure of it). If you come to whether that it is the problem, then kindly inform me.

Cheers!!!

1 Like

Please read the comments. The test data is wrong. You probably aren’t exceeding the memory limit.

1 Like

@superty Well, if the test data is really wrong,then why is it showing “SEGMENTATION FAULT” instead of “WRONG ANSWER”???

There is some problem on the server. I checked the test data for myself and my program was showing the correct answer. The output file, too, was incorrect.

Incorrect test data can result in segfault because your program can’t handle the wrong test data. e.g. N <= 100 and the test data is N = 1000 or something.

1 Like

Well I’m not so sure about the test cases being faulty. I implemented a simple BFS and it gets 100 on the grader with no issues.

In case you want to check -
http://pastebin.com/JMmvUXJ2

They’ve now fixed the test data. The same program which failed previously works now.

(not that the last comment on this thread is dated 23rd Jan)