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;
}

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