P10350 [PA 2024] Modernization of Bajtocja

PA 2024 1A

**This problem is translated from [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Round 1 [Modernizacja Bajtocji](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/mod/).** Byteland is becoming modern. The latest government program aims to provide computers to residents of towns and villages who do not have one. Byteasar is supervising the modernization of one village in this program—Bytetown—where currently no resident owns a computer. Bytetown has $n$ residents. For simplicity, Byteasar numbers them with integers from $1$ to $n$. Initially, no resident has a computer. Byteasar’s task is to process three types of events: - $\texttt{+}\ a_i\ b_i$: A computer is delivered to a resident of Bytetown. However, Byteasar does not know whether it was delivered to resident $a_i$ or resident $b_i$. It is possible that $a_i = b_i$—in that case, the computer was definitely delivered to resident $a_i$. What is certain is that the computer was delivered to someone who does not currently have a computer. - $\texttt{-}\ c_i$: The computer of resident $c_i$ breaks. It is certain that this resident had a computer before (but no longer has one now, so they may receive a new one in the future). - $\texttt{?}\ d_i$: Using **all information obtained so far**, Byteasar needs to determine for resident $d_i$ whether they definitely have a computer, definitely do not have a computer, or it is uncertain whether they have a computer. Write a program to help Byteasar answer the queries. Note: Right before a resident’s computer breaks, Byteasar does not necessarily know for sure that the resident has a computer. In other words, before a resident’s computer breaks, it may be impossible to determine from earlier events whether they have a computer.

The first line contains two integers $n$ and $q\ (1\le n\le 300\, 000, 1\le q\le 1\,000\,000)$, denoting the number of residents in Bytetown and the number of events Byteasar must process. The next $q$ lines describe the events in chronological order. In all events, $1 \le a_i,b_i,c_i,d_i \le n$. It is guaranteed that Byteasar will be asked at least once, i.e., the input contains at least one `?`. It is also guaranteed that there is at least one computer delivery event, that in every delivery the computer is always given to someone who does not currently own a computer, and that in every break event the resident always has a computer at the moment it breaks.

Output a string whose length equals the number of `?` events. If in the $i$-th query the resident definitely has a computer, then the $i$-th character of the string should be `1`. If the resident definitely does not have a computer, then the $i$-th character should be `0`. If it cannot be determined whether the resident has a computer, then the $i$-th character should be `?`.

At the beginning no one has a computer, so the answer to the first query is “no”, and the first character is `0`. Then two computers are delivered, and we are asked whether another resident has a computer. It is possible that one of the two computers delivered so far was given to them, but it is also possible that the computers were given to the first and the third residents. Therefore, we cannot determine whether the second resident has a computer, so the answer is `?`. Note that after the next delivery, the second resident definitely has a computer, but at the time of asking Byteasar, he does not know that. Translated by ChatGPT 5