# 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.

//