The Incredible Machine
All submissions for this problem are available.
With the advancement of technology, humans have designed and developed a large variety of machines to do their work. The machines can not only do the work much faster than any human but with supreme accuracy. The defence systems of a country have also moved on to using some machines or computer programs to predict and prevent any attacks to the nation. This time, one of the final year students at IIT Kanpur this year has been asked by the President during his last visit to program an intelligent machine, to help the defence forces of India against a terrorist attack.
The defense forces of India have gathered top secret intel that the terrorists may try to attack some of these particular cities to affect the flow of water streams from those cities to other cities inside the country to create havoc in the normal day to day life of the citizens. Some of our soldiers by risking their life have gathered the information that the terrorists have been using to plot such an attack. They have recovered a file which contains the map of cities that the terrorists have, the water streams following between them and possible target locations and their corresponding cities that they want to affect. The defence forces are interested to know if the terrorists will in real be able to disturb the water flow at some city that they want to affect by attacking its corresponding target city.
The defence forces also know a encoding strategy of the terrorists. They know that if some attack planned by the terrorist to disrupt flow from city A to city B is not possible than reverse disruption, i.e., from city B to city A is possible.
The student is asked to program a machine which will take this file recovered from the terrorists and output for each of the terrorist plan, whether it is possible or not. The file consists of entries of two kinds, and is a model with a total of N cities. Each city is provided with a unique number from 1 to N. The water streams can originate at some city and can end at some city. Also, all the water streams entering at a particular city combines at that city and may flow out to multiple other cities. Note that the nature assures that no water stream can move in any circular fashion.
Any city is affected by an attack on a city if:
- It is the attacked city itself.
- It is receiving water directly from the targeted city
- It is receiving water from any other affected city
The two kinds of entries in the file are as follows:
- The first kind of entries are denoted by U and are followed by two integers (x y, the unique identifiers of 2 cities) which means that water directly flows from the city x to city y.
- The second kind of entries are denoted by Q followed by two integers x and y, meaning that the terrorists are planning to attack city x in hope to disturb water supply at city y
The file provided to the student, the same one the defence forces acquired from the terrorists is a mix of these two types of entries. The terrorists, trying to be smart, have mixed up these entries i.e. they can have entries of type U and then Q and then U again and so on.
The defence forces know that this file is authentic. They want to know for each entry of type Q for cities a and b (i.e. the terrorists aim to attack city a to disturb water at city b) whether the terrorists can do so, or not. The defence forces have also identified a trick in these entries which is if it is not possible to disturb b by attacking a, it is possible to disturb a by attacking b. And if this is the case, the terrorists have inverted the order of cities in the subsequent entries of kind U. That is, if the entry Q A1 B1 results in Not possible, than the following entries U A2 B2 denotes a direct flow from B2 to A2. Note that if another following entry Q results in not possible, then the order in the following U entries is reversed again, i.e., it returns to the original order.
Help the student to program such a machine to figure out the terrorists plan.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases is given below
- The first line of each test case contains a single integer N denoting the number of cities in the file.
- Then follows the file acquired by the defence system. Each line is one of the following:
- U a b
U followed by two space separated integers a and b, meaning the file mentions that there is a direct water stream from city a to city b.
- Q a b
Q followed by two space separated integers a and b, meaning that the file mentions that the terrorists are interested in attacking city a to disturb water stream at city b.
A string "END" (without quotes), denoting the end of this test case.
- U a b
- For each entry of the form "Q a b", print "YES" (without quotes) if it is possible to disturb water stream at city b by attacking city a, otherwise print "NO"(without quotes) in a separate line.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 4000
- 1 ≤ a, b ≤ N
- The total number of lines in any test file will be bounded atmost 500000
Input: 2 5 U 1 2 U 2 5 Q 5 1 U 4 3 U 3 2 Q 1 4 Q 5 2 U 1 4 Q 1 5 END 3 U 1 2 Q 1 2 Q 2 1 U 2 3 Q 2 3 END
Output: NO YES NO YES YES NO NO
First a flow is established from city 1 to city 2 and from city 2 city 5.
After that, for Q 5 1, since there is no flow from city 5 to city 1, answer is "NO", and following U entries are reversed.
Then, flow is established from city 3 to city 4 and from city 2 city 3.
For Q 1 4, since there is a flow from 1 -> 2 -> 3 -> 4, the answer is "YES".
Similarly the rest of the queries and updates are handled.
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions