Problem E
All Just A Dream

Picture in Public Domain via Wikimedia Commons
A common plot device in story-telling is the “All Just A Dream” trope. Typical symptoms of this trope being used are talking lions, main characters dying, yodeling aliens on monocycles, and a general plethora of weird events. Then, of course, someone wakes up and it is revealed that everything that happened during the entire season did in fact not happen at all. It was All Just A Dream (or some kind of hallucination), and the days of our lives spent watching all those episodes are lost forever. In order to cause further confusion and uncertainty, this can also be done in layers, with characters having dreams within dreams within dreams, and so on.

When the All Just A Dream trick is taken too far and gets used too often, it can get difficult to keep track of what has actually happened. This is where you enter the picture. You will be given a list of events, dreams, and scenarios. Each scenario specifies some events that have happened and some others that have not happened. Your job is to determine for each scenario whether that scenario is possible (possibly using the All Just A Dream trick).


The first line of input consists of an integer $0 \le n \le 50\, 000$, the number of events, dreams and scenarios. Then follow $n$ lines, giving the events, dreams, and scenarios in chronological order. Each line is in one of the following forms:

  • An event line is of the form “E $e$”, indicating that event $e$ happens (see below for format of $e$).

  • A dream line is of the form “D $r$”, indicating that the last $r$ events that happened were All Just A Dream. Note that these events are now considered to not have happened, so they should not be counted when processing subsequent D lines.

  • A scenario line is of the form “S $k$ $e_1$ $\ldots $ $e_ k$”, where $1 \le k \le 30$ is an integer giving the number of events and $e_1, \ldots , e_ k$ is the list of events of the scenario. In a scenario, each event may be prefixed with a ‘!’, indicating that the event did not happen in this scenario.

Events are strings containing at most $20$ characters and using only the characters ‘a’-‘z’ and underscores (‘_’). For ‘D’ lines, you can assume that $r$ is an integer between $1$ and $R$, where $R$ is the total number of events that have happened so far (and that have not turned out to be a dream). For ‘E’ lines, you can assume that $e$ is not an event that has already happened, except if the previous occurence of the event turned out to be a dream, in which case it can happen again.


This problem has somewhat large amounts of input and output. We recommend you to make sure that your input and output are properly buffered in order to make the most of the few seconds of execution time that we give you.


For each scenario in the input, output a line as follows:

  • Yes” if the given scenario is consistent with what has happened so far.

  • $r$ Just A Dream” if the given scenario would be consistent with what has happened so far, provided a “D $r$” line had occurred just before the scenario. If there are many possible values of $r$, choose the smallest value. Note that you should not consider this hypothetical “D $r$” line to have occurred (as illustrated by sample input 2 below).

  • Plot Error” otherwise.

Sample Input 1 Sample Output 1
E business_as_usual
E bobby_dies
S 1 bobby_died
E stuff_happens
E jr_does_bad_things
S 2 !bobby_dies business_as_usual
E it_goes_on_and_on
D 4
S 1 !bobby_dies
S 2 !bobby_dies it_goes_on_and_on
Plot Error
3 Just A Dream
Plot Error
Sample Input 2 Sample Output 2
S 1 !something
E one
E two
E three
E four
E five
S 3 three !four one
D 1
S 3 three !four one
D 1
S 3 three !four one
2 Just A Dream
1 Just A Dream

Please log in to submit a solution to this problem

Log in