1 / 3
Sep 2012

Hi
i don't understand :
- SIGABRT meaning.
- where is the problem exactly in my code.

spoj.pl/problems/KFSTB

#include <iostream>
using namespace std;
class point
{
private :
	int R[10000],r;
public:
	point()
	{
		r=-1;
	}
	void add(int i)
	{
		++r;
		R[r]=i;
	}
	void go(point* B,int* NUm,int t)
	{
		for(int k=0;k<=r;++k)
		{
			if(R[k]==t) ++*NUm;
			else B[R[k]].go(B,NUm,t);
		}
	}
};
int main()
{
	int d,c,b,s,t,x,y,N;
	scanf("%d",&d);
	for(int i=0;i<d;++i)
	{
		N=0;
		cin>>c>>b>>s>>t;
		point* A=new point [c];
		for(int j=0;j<b;++j)
		{
			cin>>x>>y;
			A[x-1].add(y-1);
		}
		A[s-1].go(A,&N,t-1);
		cout<<N%1000000007<<"\n";
    	delete[] A;
}
return 0;
}

simple explain:
class point is denoting for "camping spots" .
R :every point has R array for record numbers of points that can reach from this point by "the one way bridges".
r :a counter for R.
add : for record points in R
go : for start check from the first point in main (s) and move to other pionts according to R for each point until arrive to t and ++NUm or until k=r (wrong way)
thanks alot smile)

  • created

    Sep '12
  • last reply

    Nov '12
  • 2

    replies

  • 166

    views

  • 3

    users

  • 1

    link

Hi easy_taker,
you have to
a) implement a (sparse-) graph data structure (e.g. lists of lists). Your adjacency list is "static" (wired in sizes), it can be really big. (10000*10000*4 bytes).
b) redesign your method (compute the necessary values only once.)
bw, ncs

1 month later

Heeeey BOY!!!!
what have you done??
look here please:
in every object of point you have :

 int R[10000];

which is 40000 byte
and in every test case you do this :

point* A=new point [c];

and C <= 10000
for the worst case c=10000
you'v used 10000*40000 =400 000 000 byte
400 MB but spoj give you only 256 MB
this is your mistake... remove the code please ...
have fun ...
(thank you @czylabsonasa completely right wink )
good by

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 17 11d

Want to read more? Browse other topics in C and C++ or view latest topics.