Crowded Forest Wildlife

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2595
64-bit integer IO format: %I64d      Java class name: Main

Description

The WWF volunteers are back again to collect more wildlife from Gump Forest! Animals have moved around the forest, and some trails are getting more crowded!. Lisa finds that the same type of animal may now be found living on multiple trails connected to the same clearing.
Elsewhere in the forest trails may have no animals living on it. If a trail has no animals, the WWF truck can drive along it any time without collecting any animals. Can Lisa still guide the WWF volunteers through the forest and fill up their truck?

Input

Animals are given as words(lowercases). Clearings are given as numbers. There may be up to 500 clearings. Clearing 0 is always the entrance to Gump Forest.
The input begins with the Gump Forest trail map. Each line describes a trail between two clearings as a pair of numbers, followed by a list of animals living on the trail. There are no more than 1000 trails and the number of animals on each trail will not exceed 30. Remaining lines begain with list of animals to be collected, in the order they are to be collected.

Output

For each list of animals to be collected, your program should output either ”Succeeded” if there is a path through the Gump Forest that can fill up the truck and return it to the entrance. Otherwise
your program should output ”Failed” for that list.
Hint: Don’t try to solve the problem in a brute-force manner by enumerating all possible paths through Gump Forest. (It will take too long.)

Sample Input

1 3 puma
2 3 lynx
0 3 toad
0 1
0 2
puma lynx
lynx toad
puma lynx toad
1 0 puma
1 2 puma
2 0 puma
puma puma puma 
puma

Sample Output

Succeeded
Succeeded
Failed
Succeeded
Failed

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .