P9271 [CEOI 2013] Parking Lot / Splot

Translated from [CEOI 2013 Day 1](https://ceoi2013.hsin.hr/tasks/tasks_day1.pdf)。 Along the Adriatic coast and its islands, there are beautiful beaches of many shapes and sizes. However, many beaches cannot be reached by car. To meet the growing demand, a huge open area near the coast was converted into a parking lot。 Since all architects involved in the design had an electrical engineering background and wanted to apply what they had learned, the layout of the parking lot ended up resembling the series-parallel diagrams commonly used in circuit design。 The parking lot consists of parking spaces and bidirectional roads connecting them. Each road connects two different parking spaces, and between any pair of parking spaces there can be at most one road. Each parking space can hold at most one car at any time. Other vehicles cannot drive through an occupied parking space。  $$\text{Figure 1: Rules for constructing a parking graph, corresponding to the three points below}$$ A series-parallel parking lot (also called a splot; hereafter called a parking graph) is a parking lot with two special parking spaces called the source and the sink. It is built from a single parking space using the series-parallel composition rules. Each parking graph can be specified by an encoding that describes its structure and the positions of parked cars. The encoding is a character sequence. Valid parking graphs and their encodings are defined recursively as follows: 1. A parking lot containing only one parking space and no roads is a valid parking graph. This single parking space is both the source and the sink of the parking graph. If the parking space is empty, the encoding is the lowercase letter `o`; if it is occupied by a car, the encoding is the lowercase letter `x`。 -  2. If $G_1$ and $G_2$ are two valid parking graphs, then their series composition $G$ is also a parking graph. The series composition is obtained by adding a road between the sink of $G_1$ and the source of $G_2$. The source of the new parking graph $G$ is the source of $G_1$, and the sink is the sink of $G_2$. If $E_1$ and $E_2$ are the encodings of parking graphs $G_1$ and $G_2$, respectively, then the encoding of $G$ is `SE1E2#`. In other words, the encoding is obtained by concatenating the uppercase letter `S`, the encodings of the component parking graphs, and the hash symbol `#`。 -  3. If $G_1$ and $G_2$ are two valid parking graphs, then their parallel composition $G$ is also a valid parking graph. The parallel composition is obtained by adding two new parking spaces $s$ and $t$, adding roads from $s$ to the sources of $G_1$ and $G_2$, and adding roads from $t$ to the sinks of $G_1$ and $G_2$. The source of the new parking graph $G$ is the newly added parking space $s$, and the sink of $G$ is the newly added parking space $t$. If $E_1$ and $E_2$ are the encodings of parking graphs $G_1$ and $G_2$, and $E_s$ and $E_t$ are the encodings of the source $s$ and the sink $t$ (the lowercase letter `o` if the corresponding space is empty, otherwise the lowercase letter `x`), then the encoding of $G$ is `PEs|E1E2|Et#`. In other words, the encoding is obtained by concatenating the uppercase letter `P`, the encoding of the source parking space, the vertical bar `|`, the encodings of the component parking graphs, another vertical bar `|`, the encoding of the sink parking space, and finally the hash symbol `#`。 -   $$\text{Figure 2: The parking graph corresponding to the first sample test below}$$ For example, the encoding of the parking graph shown above is `Po|Px|Sxo#Soo#|o#Soo#|o#` (translator’s note: `{Po|[Px|(Sxo#)(Soo#)|o#](Soo#)|o#}`)。Note that in the encoding of a parking graph $G$, the number of lowercase letters (`o` or `x`) is always equal to the number of parking spaces in $G$, and there is a one-to-one correspondence between the parking spaces in the parking graph and the lowercase letters in its encoding. The parking lot has only one exit, located at the **source parking space** of the entire parking graph. If a car can reach the source parking space through some roads and empty parking spaces (that is, it can leave the parking graph), then we say the car is not blocked. For example, in the parking graph above, neither car is blocked, but if we park a car at the sink of the parking graph (the rightmost node), then one of the cars will be blocked. It is allowed to park a car at the source parking space of the parking graph (but if you do so, all other cars in the parking graph will be blocked)。

The parking lot operator wants to arrange incoming cars in such a way that no car in the graph is blocked。 Write a program that computes the maximum total number of cars that can be parked in the given parking lot (**including the cars already there**), such that no car is blocked, and without moving any car that is already there. In addition, the program should **find a way** to park the maximum number of cars in the parking graph。

The input consists of one line containing a sequence of at least $1$ and at most $10^5$ characters, representing the encoding of the given splot. The sequence contains only uppercase letters `P` and `S`, lowercase letters `o` and `x`, and the characters `#` (`ASCII 35`) and `|` (`ASCII 124`). According to the rules above, the input will be an encoding of a splot. The input guarantees that the cars already in the parking lot are not blocked。

The output should contain $2$ lines. The first line should contain an integer $m$, the maximum number of cars that can be parked in the splot。 The second line should contain a character sequence describing an optimal final arrangement of cars in the splot. This sequence must contain exactly $m$ letters `x`, and it should be obtained by replacing some of the original letters `o` with `x`。 There may be multiple optimal arrangements, and the program may output any of them。

See the sample explanation in the last part of the Description。 If the output is incorrect or incomplete, but the first line of output (the maximum number of cars) is correct, you will receive $80\%$ of the score for the corresponding test points。 In $30\%$ of the test points, the total number of parking spaces in the splot is at most $20$。 In another $40\%$ of the test points, the splot is empty, i.e. the input contains no letter `x`。 For $100\%$ of the testdata, the encoding of the given splot contains at most $10^5$ characters。 SPJ provider: @[cff_0102](https://www.luogu.com.cn/user/542457) 。 Translated by ChatGPT 5