Dilku and Hospital
All submissions for this problem are available.
Dilku as we all know is very serious about competitive programming. In of his recent trainings he came across an interesting problem from a previous year contest. The problem was as follows :
You are writing a personnel management tool for a large hospital. One of
the problems is managing the vacation plans of employees.
There are two types of nurses working in the hospital:
staff nurses continuously take care of the patients and
special nurses fill special positions like
``surgical nurse'' or ``nurse supervisor''.
When a staff nurse goes on vacation, nothing critical happens, because
other nurses will do her work. But when special nurse goes on vacation,
she must be substituted. For every special nurse there is a list
of nurses, who can substitute her. If the substituting nurse is a special
nurse too, then some third nurse must substitute her as well, and so on.
Sometimes it is impossible for special nurse to go on
vacation, because there is no sequence of substitutions, after
that all special nurse positions are filled.
Consider the following example. There are seven nurses in
a hospital. Alice, Bob, Clara, Dona and Emma are special
nurses, Fiona and Gloria are staff nurses. They can substitute
each other according to the following scheme (arrow from
A to B means A can substitute B):
In this example, Dona and Emma cannot go on vacation, because
if one of them does, another cannot fill both positions.
Alice, Bob and Clara can go on vacation, but Bob and Clara cannot
do it at the same time, because Gloria cannot substitute them
Your task is to find all nurses who cannot go on vacation,
and all pairs of nurses, such that both can go on vacation, but not
in the same time.
Dilku thought a lot about the problem but could not solve it. The issue was that he had read the constraints of the problem wrong (After all , he is almost always thinking about his love Bhopu ! ). Dilku is very tired thinking about the problem and asks you for help. Can you solve this problem for the constraints Dilku misread ? (Constraints mentioned below)
The first line of the input file contains two integer numbers n and
k~--- the total number of nurses and number of special nurses.
Nurses 1 ... k are special nurses, and nurses
k+1 ... n are staff nurses (1 <= k < n <= 100000).
Next k lines contain the lists of possible substitutions.
The first number in (i+1)-th line is di~--- the number of nurses,
who can substitute i-th nurse. Following di numbers in the same line
are the indices of substituting nurses.
The total length of all lists does not exceed 200000.
First output the number of nurses who cannot go on vacation. Then output
their indices in increasing order.
After that, output the number of pairs of nurses, such that both can go on
vacation, but not at the same time.
Input: 7 5 2 6 7 1 7 2 2 7 1 5 1 4 Output: 2 4 5 3
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.