CCO '09 P3 - Beware the Geoducks

View as PDF
Submit solution
Points: 10
Time limit: 0.6s
Memory limit: 128M
Problem type
Canadian Computing Competition: 2009 Stage 2, Day 1, Problem 3

After perfecting the art of converting water to working C++ code, Stan Velikiy is once again facing his arch-nemesis, Mario the Wabbit. At the moment, Stan is chasing Mario on a circuit and you, as the amused observer, are being asked to predict the outcome.

The circuit can be thought as of series of nodes connected by wires of specified length. Stan and Mario each start at one of the nodes and travel along the nodes in a predetermined plan. They visit the nodes according to the plan, travelling along the wires at a speed of one meter per second. Once their travel plans run out, they stay stationary at that node.

If Stan and Mario are ever in the same location, Stan will apprehend Mario. If Stan exceeds a time limit of t he gives up and goes back to converting more water into C++ code.

Unknown to either Stan or Mario, there is a series of geoducks sitting at various nodes of the circuit. Even though they look harmless, they are remnants of top-secret experiments on the Infinite Ambiguity Drive which causes whoever reaches them to disappear instantly. Once either Mario or Stan disappear, Stan can never find Mario. Note that if Stan finds Mario on a node with a geoduck, they both disappear and Stan never finds Mario.

Input Specification

The first line contains six integers: V, the number of nodes (0 \le V \le 100); E (0 \le E \le 1\,000), the number of wires; S and M (1 \le S, M \le 1\,000), the number of nodes in the routes taken by Stan and Mario, respectively; G (0 \le G \le 100), the number of geoducks; and t (0 \le t \le 1\,000), the time limit.

The next E lines contain 3 integers per line, specifying two nodes that a wire connects and the length l (1 \le l \le 2\,000) of the wire. No wire connects a node to itself and there is at most one wire between two nodes.

The next S lines contain one integer per line, which indicate the nodes of Stan's route in the order of being visited.

The next M lines contain one integer per line, the nodes of Mario's route in the order of being visited.

The last G lines contain one integer per line, where each line indicates the location (node) where there is a geoduck.

Output Specification

On one line, output YES if Stan catches Mario before the time limit expires, NO otherwise.

Sample Input

3 1 2 2 1 3
1 2 6
1
2
2
1
3

Description of Sample Input

Stan travels from node 1 to 2 while Mario moves in the other direction. There is a geoduck on node 3.

Output for Sample Input

YES

Description of Output for Sample Input

Stan catches the Mario just as time expires, and fortunately none of them ever find a geoduck.

Comments


  • 1
    const  commented on June 21, 2019, 3:27 p.m.

    I don't understand the sample input.

    If the wire between nodes 1 and 2 has a length of 6, won't it take 6 seconds to traverse?

    Since the time limit is 3 seconds, won't Stan run out of time and not catch Mario?


    • 5
      xiaowuc1  commented on June 21, 2019, 9:18 p.m.

      At the bottom of the problem statement, the description of output for sample input explicitly says that Stan catches the Mario just as time expires. You are correct in assessing that the wire between nodes 1 and 2 has length 6, and so it would take 6 seconds for one person to traverse the entire length of the wire.

      If you read the description of the sample input, you'll note that Stan starts at node 1 and travels to node 2, and Mario starts at node 2 and travels to node 1. In three seconds, both of them will have traveled exactly half the distance of the wire, but because they started at opposite ends of the wire, they meet at the midpoint of the wire after 3 seconds, just as time expires.