codeforces-scrape

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

2146B.md (2918B)


      1 Source: https://codeforces.com/problemset/problem/2146/B
      2 
      3 B. Merging the Sets
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given $n$ sets $S_1,S_2,\ldots,S_n$, where each element in the sets is an integer between $1$ and $m$.
     22 
     23 You want to choose some of the sets (possibly none or all), such that every integer between $1$ and $m$ is included in at least one of the chosen sets.
     24 
     25 You have to determine whether there exist at least three ways to choose the sets.
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     30 
     31 The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 5\cdot 10^4$, $1\le m \leq 10^5$) — the number of sets and the upper bound of the integers in the sets.
     32 
     33 Then $n$ lines follow, the $i$-th line first containing an integer $l_i$ ($1\le l_i\le m$) — the size of set $S_i$.
     34 
     35 Then $l_i$ integers $S_{i,1}, S_{i,2}, \ldots, S_{i, l_i}$ follow in the same line ($1\le S_{i,1} \lt S_{i,2} \lt \cdots \lt S_{i, l_i}\le m$) — the elements of set $S_i$.
     36 
     37 Let $L=\sum\limits_{i=1}^n l_i$. It is guaranteed that:
     38 
     39 * The sum of $n$ over all test cases does not exceed $5\cdot 10^4$;
     40 * The sum of $m$ over all test cases does not exceed $10^5$;
     41 * The sum of $L$ over all test cases does not exceed $2\cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, print "YES" if there exist at least three ways to choose the sets. Otherwise, print "NO".
     46 
     47 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 6
     55 
     56 3 2
     57 
     58 2 1 2
     59 
     60 1 1
     61 
     62 1 2
     63 
     64 4 10
     65 
     66 3 1 2 3
     67 
     68 2 4 5
     69 
     70 1 6
     71 
     72 4 7 8 9 10
     73 
     74 2 5
     75 
     76 4 1 2 3 4
     77 
     78 4 1 2 3 4
     79 
     80 5 5
     81 
     82 5 1 2 3 4 5
     83 
     84 5 1 2 3 4 5
     85 
     86 5 1 2 3 4 5
     87 
     88 5 1 2 3 4 5
     89 
     90 5 1 2 3 4 5
     91 
     92 5 10
     93 
     94 4 1 2 3 4
     95 
     96 5 1 2 5 6 7
     97 
     98 5 2 6 7 8 9
     99 
    100 4 6 7 8 9
    101 
    102 2 9 10
    103 
    104 5 5
    105 
    106 1 1
    107 
    108 1 2
    109 
    110 1 3
    111 
    112 2 4 5
    113 
    114 1 5
    115 ```
    116 
    117 Output
    118 
    119 ```
    120 YES
    121 
    122 NO
    123 
    124 NO
    125 
    126 YES
    127 
    128 YES
    129 
    130 NO
    131 ```
    132 
    133 Note
    134 
    135 In the first test case, there are $5\ge 3$ possible ways to choose the sets:
    136 
    137 * $S_1$ — both $1$ and $2$ are included in $S_1$;
    138 * $S_1$ and $S_2$ — $1$ is included in $S_1$ and $S_2$, and $2$ is included in $S_1$;
    139 * $S_1$ and $S_3$ — $1$ is included in $S_1$, and $2$ is included in $S_1$ and $S_3$;
    140 * $S_2$ and $S_3$ — $1$ is included in $S_2$, and $2$ is included in $S_3$;
    141 * $S_1$, $S_2$, and $S_3$ — $1$ is included in $S_1$ and $S_2$, and $2$ is included in $S_1$ and $S_3$.
    142 
    143 Note that it is invalid to choose $S_2$ only because $2$ is not included in $S_2$.
    144 
    145 In the second test case, the only way is to choose all the sets.
    146 
    147 In the third test case, $5$ does not appear in any of the sets, so there is no way to choose the sets.
    148 
    149 In the fourth test case, choosing any non-empty collection of the sets is valid, so the number of ways is $2^5-1=31\ge3$.