HDELIVER: Getting TLE repeatedly

I am continuously getting Time-limit Exceeded.I used the Breadth First Search (BFS).How to optimize it.
http://www.codechef.com/problems/HDELIVER

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#define MAX 110
using namespace std;
int friendList[MAX][MAX];
int isover=0;
int startup;
int done[MAX];
vector< vector<int> > path( 101, vector<int>(101));
void reset(int length)
  {

path.clear();
path.resize(MAX);
for(int i=0;i<=length+1;++i)
for(int j=0;j<=length+1;++j)
friendList[i][j]=0;

  }
   void runBFS(int curr,int terminates,int length)
   {
	int q[MAX];
	int start=0, end=0;
	int dist[MAX];
	for(int i=0;i<length;i++)
	{
		dist[i] = -1;
		q[i]=0;
	}
	dist[curr]=0;
	q[0] = curr;
	int sumDistance = 0;
	while(start<=end)
	{
			int currEle = q[start++];
			path[startup].push_back(currEle);
			
		for(int i=0;i<length;i++)
		{
			if(friendList[currEle][i] == 1 && dist[i]==-1)
			{
				dist[i]=dist[currEle]+1;
				sumDistance += dist[i];
				q[++end] = i;
			}
		}
	}
	
}
   int main()
   {
int T,v,e,v1,v2,start,Q;
cin>>T;
while(T--)
{
	
	int terminates;
	cin>>v>>e;
	reset(v);
	for(int i=0;i<=v+1;++i)
	done[i]=0;

	for(int i=1;i<=e;++i)
	{
		cin>>v1>>v2;
		friendList[v1][v2] = 1;
		friendList[v2][v1] = 1;
	}
	cin>>Q;
	for(int i=1;i<=Q;++i)
	{
		cin>>start>>terminates;
		startup=start;
		if(done[startup]==0)
		{
			runBFS(start,terminates,v);
			done[startup]=1;
		}
		isover=0;
		for(int j=0;j<path[startup].size() && isover==0;++j)
		{
			//cout<<path[startup][j]<<" ";
			if(path[startup][j]==terminates)
			isover=1;
		}
		if(isover==1)
		cout<<"YO\n";
		else cout<<"NO\n";
	}

}

return 0;
   }
3 Likes

Did you read the last line in the problem statement
The problem setter has strictly mentioned the following Warning ::
Warning!
There are large input and output files in this problem. Make sure you use fast enough I/O methods.

Please note scanf run quite a lot faster than cin and printf run several times faster than cout.

Go through this wonderful discussions to know WHY.
Change cin to scanf and cout to printf ,then u surely wont’t get time limit as rest of the things are pretty fine.

Hope this Helps!

4 Likes

You can discuss the problem here.

//