|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
Anna loves coding multithreaded backend services. In such a service, multiple threads may sometimes need to read and write the same data structures in memory. To ensure all threads have a consistent view of a single datastructure, one can use so-called mutexes to protect access to it.
A mutex is an object that threads can acquire and release. When a mutex is acquired, the mutex cannot be acquired again until it is released -- even by the same thread! If a thread attempts to acquire a mutex it has already acquired, the thread will deadlock, waiting for itself to release the mutex.
Anna has written a program that consists of a number of functions. Each function consists of a list of commands that execute sequentially when the function is called. The commands are each one of:
Anna is not sure if she implemented her mutexes correctly, and she wants your help to verify that three properties hold. Assuming a function
main is called at the beginning of the program, you should check that:
The first line of the input contains an integer $N$, the number of functions. This is followed by a description of all the $N$ functions.
The description of a function starts with an integer $M$ and a string $X$, meaning that there is a function named $X$ with $M$ commands. This is followed by $M$ lines, each containing a command. The commands will be of the form:
acquire X-- the mutex named $X$ is acquired
release X-- the mutex named $X$ is released
access X-- a data structure that must be protected by the mutex $X$ is accessed
call F-- the function called $F$ is called
All functions and mutexes have names between $1-10$ characters in length containing only characters
a-z. No two functions will have the same name, and there will always be a function called
It is guaranteed that there is no infinite recursion: a function will never call itself, either directly or through a chain of other functions.
If the program is free from errors, output
Otherwise, output the first error that occurs during execution. Specifically:
Let $L$ denote the total number of instructions among all functions.
3 5 main acquire mutex call foo acquire mutex call foo acquire mutex 2 foo access mutex release mutex 1 bar release mutex
3 2 f acquire x call g 2 g access x acquire y 2 main call f call g
1 3 main release x acquire x access x
1 3 main access x acquire x release x