insufficient testset for problems 10039 and 10166

[vpanait]

Hi admin,
the algo for getting accepted for 10039 and 10166 is identical. Also both problems share the same issue with the test-set. I state this because I got AC with a code that does a simple BFS, however if I test the code on the following input:

5
Hamburg
Frankfurt
Darmstadt
T1
T2
2
2
0900 Hamburg
1100 Darmstadt
4
0910 Hamburg
0930 T1
1000 T2
1100 Darmstadt
0800
Hamburg
Darmstadt

it badly outputs:
Departure 0900 Hamburg
Arrival 1100 Darmstadt

If needed I can provide both good code (with a priority queue), and the bad code (with a BFS - normal queue).
Both codes get AC.

So I think adding at lest this additional test, would be a good idea for both problems.

Regards
vlad

[fersarr]

Could some one help me out a little? I keep getting Runtime Error (RE) and I can't figure out why.

Here's the code:

I tried, succesfully, the sample input and the test input provided in the post before mine by vpanait

Code: Select all

#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
#include <map>
#include <cstring>
#include <sstream>
using namespace std;


struct Trio{
	int first;
	string time1,time2; //for adjList is <edgeStart,edgeEnd> but for bfs its <currentTime,firstBoardTime>
};

Trio* newTrio(int one,string two,string three){
	Trio* trio=new Trio();
	trio->first=one;
	trio->time1=two;
	trio->time2=three;
	return trio;
}


#define MAX 110
int c,T,ti;
//queue<Trio*> bfs;

//vector<Trio* > adjList[MAX]; //nodeId,time
 

//transform hhmm to minutes to check if some time is earlier than another
int hhmmToMin(string hhmm){
	string hourStr=hhmm.substr(0,2);
	string minStr=hhmm.substr(2);
	stringstream sshour(hourStr+" "+minStr);
	int hour,min;
	sshour>>hour>>min;
	//cout<<"hour "<<hour<<" min "<<min<<endl;
	return hour*60+min;
}

int main()
{
	string city,startCity,endCity,trainTime,previousTime;
	int nodeCount=0,start,end;
	int cityId;
	while(cin>>c && c!=0){
		
		map<string,int> exists;
		vector<Trio* > adjList[c+10];
		
		for(int i=0;i<c;i++){
			cin>>city;
			if(exists.find(city)==exists.end()){
				exists[city]=nodeCount++;
			}
		}
		
		cin>>T; //train descriptions
		int previousCity,previousHr,previousMin;
		for(int i=0;i<T;i++){
			cin>>ti;
			for(int j=0;j<ti;j++){ //train stops
				cin>>trainTime;
				cin>>city;
				if(exists.find(city)==exists.end()){
					exists[city]=nodeCount++;
				}
				cityId=exists[city];
				//cout<<"timeHr "<<timeHr<<" timeMIn "<<timeMin<<" "<<city<<endl;				
				if(j>0){
					adjList[previousCity].push_back(newTrio(cityId,previousTime,trainTime));
				}
				previousCity=cityId;
				previousTime=trainTime;
			}	
		}
		
		string wakeUpTime;
		cin>>wakeUpTime;
		cin>>startCity;
		cin>>endCity;
		if(exists.find(startCity)==exists.end()){
			exists[startCity]=nodeCount++;
		}
		if(exists.find(endCity)==exists.end()){
			exists[endCity]=nodeCount++;
		}
		start=exists[startCity];
		end=exists[endCity];
		
		string answer="No connection";
		int bestTime=1<<30-1;
		//hhmmToMin(wakeUpTime);
		
		queue<Trio*> bfs;
		
		bfs.push(newTrio(start,wakeUpTime,wakeUpTime)); // node,currentTime,firstTrainTime
		while(!bfs.empty()){
			Trio* trio=bfs.front();
			int node=trio->first;
			string currentTime=trio->time1;
			string firstTime=trio->time2;
			bfs.pop();
			
			
			int diff=(hhmmToMin(currentTime)-hhmmToMin(firstTime));
			
			if(node==end && diff<bestTime){
				bestTime=diff;
				answer=firstTime+" "+currentTime;
			}
			
			if(diff>bestTime){
				continue;
			}
			
			vector<Trio*> neighbors=adjList[node];
			vector<Trio*>::iterator it;
			for(it=neighbors.begin();it!=neighbors.end();it++){
				int nextNode=(*it)->first;
				string edgeTime1=(*it)->time1;
				string edgeTime2=(*it)->time2;
				if(hhmmToMin(currentTime)<=hhmmToMin(edgeTime1)){
					if(firstTime==wakeUpTime){
						bfs.push(newTrio(nextNode,edgeTime2,edgeTime1));
					}
					else{
						bfs.push(newTrio(nextNode,edgeTime2,firstTime));
					}	
				}
			}
		}
		
	
		cout<<answer<<endl;
	
	
	
	}








	return 0;
}

[brianfry713]

The very first line of the input gives the number of scenarios.