codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]$.