P5841 [CTSC2011] String Rearrangement

For two strings $A = a_1 a_2 \cdots a_n$ and $B = b_1 b_2 \cdots b_n$, define the length of their longest common prefix $\text{lcp}(A,B)$ as follows: $$\text{lcp}(A,B) = \max \{k|0 \le k \le n,k \le m,a_1 a_2 \cdots a_k = b_1 b_2 \cdots b_k \}$$ Given $n$ pairwise distinct non-empty strings $S_1,S_2,\cdots , S_n$ consisting of lowercase letters, for a permutation $P=(p_1,p_2,\cdots,p_n)$ of $1$ to $n$, define the value $W(P)$ as: $$W(P) = \sum_{i=2}^n (\text{lcp}(S_{p_{i-1}},S_{p_i}))^2$$ Let a permutation that can produce the maximum value be $P^*_G$. In addition, there are $q$ extra tasks. For the $i$-th task, two different integers $X_i$ and $Y_i$ between $1$ and $n$ are given. For a permutation $P$, if under the condition that $W(P) = W(P^*_G)$, it also satisfies that the $X_i$-th string $S_{X_i}$ is placed immediately before the $Y_i$-th string $S_{Y_i}$, i.e. $\text{pos}(S_{X_i}) + 1 = \text{pos}(S_{Y_i})$, where $\text{pos}(S_i)$ denotes the position of string $S_i$ in the permutation, then the permutation $P$ will additionally receive a reward of $2^i$. The sum of rewards of all tasks is called the total task reward. Let a permutation that can maximize the total task reward be $P^*_B$. Find: 1. $W(P^*_G)$, the maximum value possible. 2. $P^*_B$, a permutation that, while ensuring the maximum value, can maximize the total task reward.

The first line contains two integers $n$ and $q$, representing the number of strings and the number of extra tasks, separated by a space. In the next $n$ lines, the strings are given. The $i$-th line contains a string $S_i$. In the next $q$ lines, the extra tasks are given. The $i$-th line contains two integers $X_i$ and $Y_i$, separated by a space.

The output contains three lines. The first line contains a non-negative integer $W(P^*_G)$. The second line contains several numbers separated by single spaces. The first number is the number of satisfied extra tasks $k$, followed by $k$ numbers which are the indices of these tasks. The indices start from $1$ and must be output in increasing order. The third line contains $n$ positive integers separated by spaces, representing a permutation $P^*_B$ of $1$ to $n$.

**Scoring** For each test point: - If the first line of the output file is correct, you can get $2$ points. - If the second line of the output file is correct, you can get $4$ points. - If the third line of the output file is correct, you can get $4$ points. - If all three lines are correct, you can get $10$ points. For the permutation in the third question, if multiple solutions exist, outputting any one of them will be accepted. If you cannot complete some part, please still output according to the required format to avoid judging failure. **Constraints** - For $10\%$ of the data, $n \le 10$, $q = 1$, and each string length is at most $50$. - For $20\%$ of the data, $n \le 50$, $q = 1$, and each string length is at most $50$. - For $50\%$ of the data, $n,q \le 1000$, and each string length is at most $1000$. - For $70\%$ of the data, no string is a prefix of any other string. - For $100\%$ of the data, $n \le 4 \times 10^4$, $q \le 10^5$, each string length is at most $10^4$, and the sum of all string lengths is at most $2 \times 10^5$. Translated by ChatGPT 5