Help needed!

What is crash?(stack overflow)
what to do?I use normal dfs and pass just two variables to it:(((

write dfs without recursion

or you can just add
  {$M 16777216} for Pascal
and
  #pragma comment(linker, "/STACK:16777216") for C/C++
to your recursive solution.

Thank you very much, I don't know how to express my thanks to you! Thanks !!!

I also got Crash on Test #3. I use BFS with a global queue, and global vectors and arrays. Does anybody know why my program crashes. Here's my code:


#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int a[5000][5000];
int dist[5000][5000];
vector <int> v[5000];
vector <int> used;
queue <int> q;
int parent[5000];
int n,m;
int usd[5000];

void input() {
    scanf("%d",&n);
    int x,y,c;
    for (int i=0;i<n-1;i++) {
        scanf("%d%d%d",&x,&y,&c);
        a[x][y]=a[y][x]=c;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}


void bld() {
    q.push(0);
    int c;
    while (!q.empty()) {
        c=q.front();
        q.pop();

//        printf("%d ",c);

        usd[c]=1;
        for (int i=0;i<used.size();i++) {
            dist[c][used[i]]=dist[used[i]][c]=a[c][parent[c]]+dist[parent[c]][used[i]];
        }

        for (int i=0;i<v[c].size();i++) {
            if (usd[v[c][i]]==0) {
//                printf("%d - %d ",v[c][i],c);
                parent[v[c][i]]=c;
                q.push(v[c][i]);
            }
        }
        used.push_back(c);
    }
}


void print() {
    scanf("%d",&m);
    int x,y;
    for (int i=0;i<m;i++) {
        scanf("%d%d",&x,&y);
        printf("%d\n",dist[x][y]);
    }
}


int main() {
    input();
    bld();

    print();
    return 0;
}

N ≤ 50000
but your arrays only 5000

I have this problem in Java. Could you help me to fix it?

My solution crashes on this test case.I used BFS+LCA to solve it,used global queue and arrays of size 50005,which should be enough,as the problem says there will be 50000 nodes.I also used randomised source for BFS,but still it's not working.Can anyone please help?
Here's my code

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
class edge{
      public:
      int to,prev,w;
      };
edge edges[100100];
int last[100100],p[50005],d[50005],L[50005],P[50005][20];
int N,num;
bool check[50005];
queue<int>Q;
void addedge(int u,int v,int w)
{
   edges[num].to=v;
   edges[num].w=w;
   edges[num].prev=last[u];
   last[u]=num;
   num++;
}
void BFS(int sc)
{
   int u,v,i;
   while(!Q.empty()) Q.pop();
   Q.push(sc);
   check[sc]=true;p[sc]=-1;d[sc]=0;L[sc]=0;
   while(!Q.empty())
   {
      u=Q.front();
      Q.pop();
      for(i=last[u]; i!=-1; i=edges[i].prev)
      {

          v=edges[i].to;
          if(!check[v])
          {
             check[v]=true;
             p[v]=u;
             d[v]=d[u]+edges[i].w;
             L[v]=L[u]+1;
             Q.push(v);
          }
      }
   }
}
int Find(int u,int v)
{
    //make u at higher level
   if(L[u]>L[v])
   {
      int temp=u;
      u=v;
      v=temp;
   }
   if(u==v) return u;

   int log,i,j;
   for(log=1; log<N; log*=2);
   //bring u and v to same level
   for(i=log; i>=0 ;i--)
     if(L[v]-L[u]>=(1<<i))
       v=P[v][i];
   if(u==v) return u;

   for(i=log; i>=0; i--){
     if(P[u][i]!=-1 && P[u][i]!=P[v][i])
      {
         u=P[u][i];v=P[v][i];
      }
   }
   return p[u];

}
int main()
{
    int m,i,j,k,a,b,c,log,x;
    //freopen("timus.txt","r",stdin);
    while(scanf("%d",&N)!=EOF)
    {
       num=0;
       for(i=0; i<N; i++) last[i]=-1;
       for(i=1; i<N; i++)
       {
          scanf("%d%d%d",&a,&b,&c);
          x=a;
          addedge(a,b,c);
          addedge(b,a,c);
       }
       for(i=0; i<N; i++) check[i]=false;
       BFS(x);
       //for(i=0; i<N; i++)  printf("%d %d %d %d\n",i,p[i],L[i],d[i]);
       memset(P,-1,sizeof(P));
       for(log=1; log<N; log*=2);
       for(i=0; i<N; i++)  P[i][0]=p[i];
       for(j=1; j<=log; j++){

         for(i=0; i<N; i++)
         {
             if(P[i][j-1]!=-1)
               P[i][j]=P[P[i][j-1]][j-1];
         }
       }

       scanf("%d",&m);
       while(m--)
       {
          scanf("%d%d",&a,&b);
          int LCA=Find(a,b);
          int dis=d[a]+d[b]-2*d[LCA];
          printf("%d\n",dis);
       }
    }

    return 0;
}

Edited by author 07.10.2012 01:43

Can anyone please help me??