CF問題集PART5 #266 div 2 E_html/css_WEB-ITnose

【原题】

E. 情報グラフ

テストごとの制限時間

1 秒

テストごとのメモリ制限

512 メガバイト

入力

標準入力

出力

標準出力

会社「X」には n 人の従業員が働いています（便宜上、1 から n までの番号を付けます）。当初、従業員同士の間には何の関係もありませんでした。次の m 日ごとに、次のいずれかのイベントが発生しました:

従業員 y が従業員 x の上司になった (その時点で、従業員 x にはそれまで上司がいませんでした);

または従業員 x が書類のパケットを受け取りましたそしてそれらに署名します。それから彼はそのパケットを上司に渡します。上司は文書に署名し、上司などに渡します (最後に文書に署名した人が文書をアーカイブに送信します)。

または、「従業員 x が特定の文書に署名するかどうかを決定する」タイプの要求が届きます。

タスクは、イベントが与えられた場合に、記述されたタイプのクエリに応答するプログラムを作成することです。その時点で、勤務時間全体を通して、会社には循環依存関係がなかったことが保証されます。

入力

最初の行には 2 つの整数 n と m が含まれています(1?≤?n,?m?≤?105 ）？従業員の数とイベントの数。

次の m 行には、それぞれ 1 つのイベントの説明が含まれます (イベントは時系列順に示されています)。行の最初の番号は、イベント t のタイプ (1?≤?t?≤?3) を決定します。

t?=?1 の場合、次に 2 つの整数 x と y (1?≤?x,?y) が続きます。 ?≤?n) ?会社の従業員の数。従業員 x には現在上司がいないことが保証されています。

t?=?2 の場合、次に整数 x (1?≤?x?≤?n)? に従います。文書パケットを受け取った従業員の番号。

t?=?3 の場合、次に 2 つの整数 x と i (1?≤?x?≤?n; 1?≤?i?≤?[数すでに与えられているパケット]) ?従業員と、情報を調べる必要がある文書パケットの番号。文書パケットには時系列順に 1 から番号が付けられます。

入力には 3 番目のタイプのクエリが少なくとも 1 つあることが保証されます。

出力

3 番目のタイプの各クエリに対して、「YES」を出力する場合従業員は文書パッケージに署名し、そうでない場合は「NO」と答えました。引用符なしですべての単語を出力します。

サンプルテスト

入力

4 91 4 32 43 3 11 2 32 23 1 21 3 12 23 1 3

出力

YESNOYES

【题意]意思看了半天~就是有人，M 個の操作。各操作には 3 種類があります。

③ x 号のファイルに落とされたハンド里がありません。

【分析】 即時、x であるかどうかを個別に判断します。しかし、その後、DFS シーケンスを使用して同じセキュリティの深さを直接取得し、同じセキュリティ上にあるかどうかを再度使用して収集することができると考えられます。