Can't figure out the reason why my program is giving runtime error on spoj but not on ideone

Question

I am solving the problem mice and maze on spoj http://www.spoj.com/problems/MICEMAZE/ I am using a simple recursive approach because the constraints are very small.

My code runs without any error on ideone but it gives a runtime error on spoj (segmentation fault). I can't figure out the problem in my code.

Here is my C++ program and I am using adjacency list to represent the graph.

#include<iostream>
#include<vector>
#include<climits>
using namespace std;
vector<pair<int,int> > graph[100];  //adjacency list , pair stores the destination node of an edge and its weight
int e,t,n,count=0,cost,visited[105];

void maze(int v,int c) //recurssive routine which checks the cost of travelling to each node until it finds the exit node.
{
    if(c>t)
        return;
    if(v==e)
    {
        if(c<=cost)
            cost=c;
        return;
    }
    for(int i=0;i<graph[v].size();i++)
    {
        if(!visited[graph[v][i].first])
        {
            visited[graph[v][i].first]=1;
            maze(graph[v][i].first,graph[v][i].second+c);
            visited[graph[v][i].first]=0;
        }
    }

}

int main()
{
    int a,b,w,m;
    cin>>n;
    cin>>e;
    cin>>t;
    cin>>m;
    for(int i=0;i<m;i++)
    {
        cin>>a;
        cin>>b;
        cin>>w;
        graph[a].push_back(make_pair(b,w));
    }
    for(int i=1;i<=n;i++)
    {
        cost=INT_MAX;
        if(!visited[i])
        {
            visited[i]=1;
            maze(i,0);
            visited[i]=0;
        }
        if(cost<=t)
            count++;
    }
    cout<<count;
    return 0;
}

Why do you make an array of `vector` objects? Use a `std::vector > >`? — tillaert, Dec 18 '14 at 12:41
What's the input ? Without that knowledge it's hard to reproduce the problem. — Jabberwocky, Dec 18 '14 at 12:42
@MichaelWalz Those kind of OJ will never give you their input, else you can just print the output and submit it. — rcs, Dec 18 '14 at 12:54

score 0 · Answer 1 · answered Dec 18 '14 at 13:01

0

You are going from 1 to n in your 2nd loop. If n is 105 then your program will get a segmentation fault.

You need to go from 0 to 104 (i=0 ; i< n).

answered Dec 18 '14 at 13:01

MichaelCMS

4,703
2
23
29

It is stated in the question that cells are numbered from 1 to 100 only. Therefore n={1,100}. – ana Dec 18 '14 at 13:57

Anton Savin · Accepted Answer · 2014-12-18T14:02:07.303

0

You run maze(i,0); with i varying from 1 to n inclusively, but if n is equal to 100 you'll go beyond graph bounds when you access graph[v].

But even if you fix this, you'll get a time limit error, because although the constraints are small, you effectively check all possible paths with given length in a graph, which is roughly O(n!) complexity.

edited Dec 18 '14 at 14:02

answered Dec 18 '14 at 13:03

Anton Savin

40,838
8
54
90

I don't get it. Even if i call maze(100,0), in the function maze() graph[100].size() will return me the size of vector at 100th position in graph. There is no way I will be accessing any graph location beyond 100 because it is mentioned in the question that cells are numbered from 1 to 100 (inclusive). – ana Dec 18 '14 at 13:53
`graph[100]` is out of bounds, the last element is `graph[99]`. – Anton Savin Dec 18 '14 at 14:01
It was a very careless mistake from my side, I did not notice that i had declared graph of size 100, I thought I had declared a size of 105 and overlooked it everytime. and the code is getting accepted in brute force also Thanks – ana Dec 18 '14 at 14:08

score 0 · Answer 3 · edited May 23 '17 at 10:26

It will be hard to tell why on one system it works and on the other don't without some more info. My guess is: memory exceeded. Note that exercises pages like SPOJ gives usually memory limit, in your case too. They wrote that N<= 100, So you can make your array fixed since 100 is not very big, but they didn't gave you limit for M! I bet they prepared tricky input with huge number for M. Memory management for vector is killer in this case because of reallocations (google for more or take a look here Does std::vector *have* to move objects when growing capacity? Or, can allocators "reallocate"?).

Can't figure out the reason why my program is giving runtime error on spoj but not on ideone

3 Answers3