問題一覧 > 通常問題

No.2780 The Bottle Imp

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 : yuusaanyuusaan / テスター : 👑 amentorimaruamentorimaru
6 ProblemId : 10977 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-25 11:18:19

ストーリー

ゆ~さんは何人かの友達と一緒に旅行に行き、夜に古い旅館に泊まりました。

そこで、雰囲気があるからと、電気を消して蝋燭に火をつけて怖い話をし始めました。ゆ~さんは話します。

「びんの悪魔って知ってるかい?誰かから買うとあらゆる願いが叶うけど手放す前に死ぬと地獄へ連れていかれるんだ。

助かるためにはそのびんを買った時より低い値段で売って手放す必要がある。それ以外の方法だと決して手放すことはできない。

もしかしたら大抵の日本人にとっては地獄の恐ろしさはハッキリとはイメージしづらいものかもしれないけど、まぁどんな願いが叶うという利をもってしても割に合わないほどつらいと考えてくれ。

さて、そんなびんがある村の若者の手に渡ってしまった。びんの恐怖は村の人全員に襲い掛かるのだろうか?」


「...っていうのを判定するコードを実装しろという話だ。怖いだろう?」

そんなもの解いてしまえば怖くないですね。解いて実力を証明しましょう。

問題文

あるところに $N$ 人が住む村があります。以下、単に村と書くときはこの村のことを表しているものとします。

村に住んでいる人には順に人 $1$ ,人 $2$ , $\dots$ , 人 $N$と番号が振られています。

また、人 $i$ $(1\leq i \leq N)$ は村に住んでいる人のうち $M_i$ 人のことを知っていて、具体的には人 $A_{i,1},A_{i,2}, \dots ,A_{i,M_i}$ を知っています。

ある日、人 $1$ の手に「びんの悪魔」が渡りました。「びんの悪魔」そのものの性質については今回の問題には関係ないので説明は省略します。

この「びんの悪魔」を手にしてしまった人は村に住む任意の誰かを知っていれば、必ずその知っている誰かを一人ランダムに選択し、「びんの悪魔」を渡します。

もし、その人が自分自身以外に村に住む全員のことを知らなかった場合は「びんの悪魔」は誰にも渡されません。

この「びんの悪魔」を渡す行動はその人にすでに $1$ 回以上「びんの悪魔」が渡っていた場合でも行われるものとします。

村に住む全ての人に $1$ 回以上「びんの悪魔」が渡る可能性はありますか?判定してください。

入力

$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}$

制約
  • $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$
  • $j \neq j'$ であるとき $A_{i,j} \neq A_{i,j'}$
  • 入力はすべて整数

出力

村の全ての人に「びんの悪魔」が一回以上渡る可能性があるならYesを、

そうでないならNoを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
5
2 2 3
3 1 3 5
2 1 2
1 5
2 2 4
出力
Yes

例として以下のように「びんの悪魔」が渡る可能性があります。

  • はじめ、人 $1$ に「びんの悪魔」が渡る。
  • 人 $1$ が人 $3$ に渡す。
  • 人 $3$ が人 $2$ に渡す。
  • 人 $2$ が人 $5$ に渡す。
  • 人 $5$ が人 $4$ に渡す。

サンプル2
入力
3
1 2
1 1
0
出力
No

人 $3$ のことを知っている人は村には存在しないので「びんの悪魔」が人 $3$ に渡る可能性はありません。

サンプル3
入力
4
1 3
0
1 4
1 2
出力
Yes

二人のうちの片方がもう片方を一方的に知っている関係が存在する可能性がある点に注意してください。

サンプル4
入力
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
出力
Yes

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。