DMOPC '16 Contest 2 P2 - Ebola Outbreak

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.3s
Java 8 1.0s
Python 1.0s
Memory limit: 64M

Problem type

It is recently discovered that someone in lolzballs's school has contracted Ebola (an extremely dangerous viral disease). The school administrators were frightened that more people would become infected and decided to isolate those who are potentially infected. They reached out to lolzballs to help them resolve their dilemma.

There are a total of N people in lolzballs's school, numbered 1 to N. There are a total of M classes, and the i'th class has a size of K_i. Each person can be part of 0 or more classes. Initially, the person numbered 1 is infected with Ebola.

A person is deemed potentially infected if:

  1. The person is already infected
  2. The person has class with the infected person
  3. The person has class with someone that is potentially infected

Please write a program to help lolzballs determine who is potentially infected.


Subtask 1 [80%]

1 \le N,M \le 100

Subtask 2 [20%]

1 \le N,M \le 10^5

For all testcases, \sum{K_i} < 10^6.

Input Specification

On the first line of the input are 2 integers N and M.

This line is followed by M lines which describes each class.

Every line begins with an integer K_i (K_i \le N), which represents the number of students in that class. K_i integers follows, indicating the number of people in the i'th class.

Output Specification

Output the number of potentially infected people on the first line of the output.

On the second line, please output the sorted list of potentially infected people, separated by a space.

Sample Input

9 4
3 1 2 3
4 2 3 4 5
3 6 7 8
2 3 9

Sample Output

1 2 3 4 5 9


  • 1
    balathegreat999  commented on Nov. 23, 2020, 6:33 p.m.

    2020: hold my corona

  • -1
    DKLS2  commented on March 11, 2017, 9:30 p.m. edited


    I don't understand what I am missing for an AC. Can someone please help.

  • 0
    deleted  commented on Nov. 8, 2016, 8:45 p.m.

    is 1 always going to be the second number on line 2?

    • 0
      jimgao  commented on Nov. 8, 2016, 9:21 p.m.

      No, it is not. The person numbered 1 can be part of any group, or no group at all.

  • 0
    kobortor  commented on Nov. 8, 2016, 4:47 p.m.

    Is there a smaller restriction on the size of K? I don't think it's even possible to input 10^5^2 = 10^10 things in 0.5s.

    • 0
      henry1  commented on Nov. 8, 2016, 4:53 p.m. edited

      Edit: read the comment wrong.

      • 0
        jimgao  commented on Nov. 8, 2016, 4:54 p.m.

        Since processing takes linear time, having N=10^{10} would be insane.

    • 0
      jimgao  commented on Nov. 8, 2016, 4:51 p.m.

      It should be 10^9. The problem statement has been corrected.

  • 17
    henry1  commented on Nov. 8, 2016, 4:46 p.m.

    Ebola isn't spread by being near someone who has it. Ebola is spread through direct contact with blood or bodily fluids from someone who has or died with Ebola.

  • 6
    P234rex  commented on Nov. 8, 2016, 4:29 p.m.

    virus is a noun viral is the adjective pls don't disqualify me

    • 0
      jimgao  commented on Nov. 8, 2016, 4:42 p.m.

      Nice catch! The wording has been corrected.