No.2780 The Bottle Imp
タグ : / 解いたユーザー数 79
作問者 :
amentorimaru
Story
Yu-san went on a trip with several friends and stayed at an old inn for the night.
There, because it suited the atmosphere, they turned off the lights, lit candles, and began telling scary stories. Yu-san speaks:
"Do you know about the Bottle Imp? If you buy it from someone, any wish you make will come true, but if you die before letting go of it, you are dragged off to hell.
To be saved, you must get rid of the bottle by selling it for a lower price than you bought it for. There is no other way you can ever get rid of it.
Perhaps for most Japanese people, the terror of hell is hard to picture clearly, but just think of it as so painful that it isn't worth it, even with the benefit of having any wish granted.
Now, such a bottle has fallen into the hands of a young person in a certain village. Will the terror of the bottle befall everyone in the village?"
"...and the task is to implement code that determines exactly that. Scary, isn't it?"
Nothing like that is scary once you've solved it. Let's solve it and prove our skill.
Problem Statement
Somewhere, there is a village where $N$ people live. Hereafter, "the village" refers to this village.
The people living in the village are numbered person $1$ , person $2$ , $\dots$ , person $N$ in order.
Person $i$ $(1\leq i \leq N)$ knows $M_i$ of the people living in the village; specifically, they know persons $A_{i,1},A_{i,2}, \dots ,A_{i,M_i}$ .
One day, the "Bottle Imp" came into the hands of person $1$ . The properties of the "Bottle Imp" itself are irrelevant to this problem, so their explanation is omitted.
A person who has come to hold the "Bottle Imp", if they know anyone living in the village, always randomly chooses one of the people they know and hands the "Bottle Imp" to that person.
If that person knows none of the other people living in the village, the "Bottle Imp" is not handed to anyone.
This action of handing over the "Bottle Imp" is performed even if the "Bottle Imp" has already been handed to that person $1$ or more times.
Is it possible that the "Bottle Imp" is handed to every person living in the village $1$ or more times? Determine this.
Input
$N$
$M_1 \ A_{1,1} \ A_{1,2} \ \dots \ A_{1,M_1}$
$M_2 \ A_{2,1} \ A_{2,2} \ \dots \ A_{2,M_2}$
$\vdots$
$M_N \ A_{N,1} \ A_{N,2} \ \dots \ A_{N,M_N}$
Constraints
- $1\leq N \leq 10^5$
- $0 \leq M_i\leq N-1$
- $\sum_{i=1}^{N} M_i \leq 10^5$
- $1\leq A_{i,j} \leq N$
- $A_{i,j} \neq i$
- $A_{i,j} \neq A_{i,j'}$ when $j \neq j'$
- All inputs are integers
Output
Print Yes if it is possible that the "Bottle Imp" is handed to every person in the village one or more times,
and No otherwise.
Sample
Sample 1
Input
5 2 2 3 3 1 3 5 2 1 2 1 5 2 2 4
Output
Yes
For example, the "Bottle Imp" may be handed over as follows.
- Initially, the "Bottle Imp" comes to person $1$ .
- Person $1$ hands it to person $3$ .
- Person $3$ hands it to person $2$ .
- Person $2$ hands it to person $5$ .
- Person $5$ hands it to person $4$ .
Sample 2
Input
3 1 2 1 1 0
Output
No
No one in the village knows person $3$ , so the "Bottle Imp" cannot be handed to person $3$ .
Sample 3
Input
4 1 3 0 1 4 1 2
Output
Yes
Note that there may be a relationship in which one of two people knows the other one-sidedly.
Sample 4
Input
10 3 5 3 2 1 8 3 7 8 4 0 3 3 10 4 6 2 9 10 5 7 8 3 1 10 3 3 10 6 5 5 6 10 3 7 5 3 8 3 7
Output
Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。