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
insufficient testset for problems 10039 and 10166
Moderator: Board moderators
Re: insufficient testset for problems 10039 and 10166
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
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: insufficient testset for problems 10039 and 10166
The very first line of the input gives the number of scenarios.
Check input and AC output for thousands of problems on uDebug!