2205C.md (3500B)
1 Source: https://codeforces.com/problemset/problem/2205/C 2 3 C. Simons and Posting Blogs 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This life is like a TV show; we're swept along as the plotlines go. 22 23 — SHUN, [TRAP](https://open.spotify.com/track/4lfS48CaivAm4QaimqbAPv) 24 25 There are $n$ blogs. The $i$-th blog mentioned $l_i$ users in order as an array $a_i=[a_{i,1},a_{i,2},\ldots,a_{i,l_i}]$. 26 27 You are going to post all $n$ blogs. Let us maintain a sequence $Q$ that describes the list of users you have recently mentioned. You need to perform the following operation exactly $n$ times: 28 29 * Choose an unposted blog $i$ ($1\le i\le n$), then post it. This will cause the following operations for each $1\le j\le l_i$ in order: 30 + If $a_{i,j}$ already exists in $Q$, then move $a_{i,j}$ to the beginning of $Q$. 31 + Otherwise, insert $a_{i,j}$ at the beginning of $Q$. 32 33 Find the lexicographically smallest$^{\text{∗}}$ $Q$ after all $n$ operations. 34 35 $^{\text{∗}}$An array $x$ is lexicographically smaller than an array $y$ if and only if one of the following holds: 36 37 * $x$ is a prefix of $y$, but $x \ne y$; or 38 * in the first position where $x$ and $y$ differ, the array $x$ has a smaller element than the corresponding element in $y$. 39 40 Input 41 42 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows. 43 44 The first line contains a single integer $n$ ($1\le n\le 3000$) — the number of blogs. 45 46 Then $n$ lines follow, the $i$-th line starting with an integer $l_i$ ($1\le l_i\le 3000$), describing the number of users mentioned in the $i$-th blog, which is followed by $l_i$ integers $a_{i,1},a_{i,2},\ldots,a_{i,l_i}$ ($1\le a_{i,j}\le 10^6$) — the list of users mentioned in the $i$-th blog. 47 48 It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$. 49 50 Denote $\sum\limits_{i=1}^n l_i$ as $L$. It is guaranteed that the sum of $L$ over all test cases does not exceed $3000$. 51 52 Output 53 54 Denote $m$ as the number of users mentioned in at least one blog. For each test case, output $m$ integers $Q_1,Q_2,\ldots,Q_m$ — the lexicographically smallest $Q$. 55 56 Example 57 58 Input 59 60 ``` 61 5 62 63 3 64 65 5 1 2 3 4 6 66 67 3 2 5 1 68 69 4 1 9 2 3 70 71 2 72 73 2 1 6 74 75 1 6 76 77 1 78 79 3 6 1 1 80 81 5 82 83 4 2 3 3 4 84 85 5 1 2 4 3 1 86 87 2 4 1 88 89 3 3 3 1 90 91 5 4 3 2 2 2 92 93 5 94 95 4 2 3 1 4 96 97 5 2 5 5 6 5 98 99 5 3 4 7 5 5 100 101 8 3 6 4 3 1 1 5 4 102 103 2 1 1 104 ``` 105 106 Output 107 108 ``` 109 1 5 2 3 9 6 4 110 111 6 1 112 113 1 6 114 115 1 3 2 4 116 117 1 4 3 2 5 6 7 118 ``` 119 120 Note 121 122 In the first test case, you can post the blogs as follows: 123 124 * Post the first blog, and $Q$ will become $[6,4,3,2,1]$. 125 * Post the third blog, and $Q$ will become $[3,2,9,1,6,4]$. 126 * Post the second blog, and $Q$ will become $[1,5,2,3,9,6,4]$. 127 128 There is another method to post blogs: 129 130 * Post the third blog, and $Q$ will become $[3,2,9,1]$. 131 * Post the first blog, and $Q$ will become $[6,4,3,2,1,9]$. 132 * Post the second blog, and $Q$ will become $[1,5,2,6,4,3,9]$. 133 134 We can see that $[1,5,2,3,9,6,4]$ is lexicographically smaller than the other one. If we do not post the second blog at the end, the first element of the array will not be $1$, so $[1,5,2,3,9,6,4]$ is the lexicographically smallest array $Q$. 135 136 In the second test case, you can post the blogs as follows: 137 138 * Post the first blog, and $Q$ will become $[6,1]$. 139 * Post the second blog, and $Q$ will keep itself $[6,1]$. 140 141 In the third test case, you have to post the only blog, and $Q$ will become $[1,6]$.