GCPC11H - Sightseeing

no tags 

As a computer science student you are of course very outdoorsie, so you decided to go hiking. For your vacation this year, you located an island full of nice places to visit. You already identified a number of very promising tracks, but are still left with some problems. The number of choices is so overwhelming, that you had to select only a "small" subset of at most 105 sights.

And if that is not enough, you are very picky about the order in which you want to visit the sights. So you have already decided on an order in which you want to visit the preselected tracks. The problem you are left with is to decide in which direction to travel along each single track, and whether you may have to reduce your choice of tracks even further. After identifying the travel time between the endpoints of different tracks, you decide to write a program to figure out if you can make all your trips within the time you have planned for your vacation. Since you also do not want to waste any precious time, you only care about an optimal solution to your problem. Furthermore, the tracks can get pretty challenging. Thats why you do not want to hike along a track more than once.


The first line of the input gives the number of test cases C (0 < C ≤ 100). The first line of each such test case holds two integers N, T the number of tracks of the current hiker (1 ≤ N ≤ 105) and the maximal time spent hiking throughout the vacation (0 ≤ T ≤ 106). Each of the following N lines holds five integers cp, cbb, cbe, ceb and cee that describe a track (in order of importance). cp gives the length of the track in minutes. cxy gives the travel time of the official begin or end of a track to the beginning or end of the next most important track, where x and y are either b or e. All values given are non-negative integers not greater than 106. Since you have to get back to your car, the list is circular. Furthermore, we will ignore the time it takes you to get to the start of your trip with your car.


For each test case print one line. The output should contain a list of either F or B for every track (in order) indicating whether you have to hike the track in forward direction or backward direction. If you cannot make the full trip within the planned time T, you should print IMPOSSIBLE to indicate that these trips are just too much hiking. You can assume that the optimal solution is always unique.


2 100
4 7 8 2 3
1 4 6 1 2
2 20
4 2 3 7 8
1 1 2 4 6
3 5
1 2 2 2 1
1 1 2 2 2
1 2 2 1 2


hide comments
Ivaylo Chernev: 2012-04-13 15:43:32

Dear Adrian , can you tell me why me O(n*logN ) solution doesnt work :S

Nenad: 2012-04-07 00:57:15

Dear Adrian, I've tried to submit the code that seems ok when I test it, and also works fine with the example given above, but i get WA at 7. test. Any suggestions?
Edit: And what about N=1? Do we suppose that he hikes along F or B, and then he takes one of the eb and be routes?

Last edit: 2012-04-07 12:21:01
Adrian Kuegel: 2011-10-24 11:54:12

I think it is because Java is slow. I have taken a short look at your code and it seems to be ok, you probably just have to optimize it; since I am no Java expert I can't help you there :-(

Korn Acker: 2011-10-22 20:37:51

Does somebody has some testcases of this problem? My solution only reach testcase nr. 9 in the judge.

Edit: i get correct on another judge, so it is maybe just slow Java

Last edit: 2011-10-22 21:33:42
Adrian Kuegel: 2011-09-19 09:08:20

if the answer is impossible, then it is unique!

Pratham Khandelwal: 2011-09-17 11:39:10

What if when N =1, then I can travel in any direction on that path.

So how will it be a unique answer?

sandeep reddy biddala: 2011-07-08 12:40:12

@adrian: thank you very much. it was very nice of you to spare considerable time for checking my code. and for those who try to solve the problem use long long.

Adrian Kuegel: 2011-07-08 10:17:35

It is one big test case that you fail. But I found the reason: you use int in your code, but the total length of the route can lead to overflow; you have to use long long.

sandeep reddy biddala: 2011-07-08 03:08:56

still getting wa....
i think i did the problem right. could someone please give me a non trivial test case. it would be very helpful.

Last edit: 2011-07-08 03:09:30
Adrian Kuegel: 2011-07-07 11:36:24

It is necessary to hike through the track (in my abstract explanation that is the part "use the edges from node 2*i to 2*i + 1 or 2*i+1 to 2*i"). Forward means from 2*i to 2*i + 1, backward from 2*i + 1 to 2*i.

Last edit: 2011-07-07 11:37:02

Added by:Adrian Kuegel
Time limit:3.295s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:German Collegiate Programming Contest 2011 (Author: Moritz Kobitzsch)