← 返回题目列表

AtCoder · joisc2017_h

H. 长宅

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

細長い屋敷 (Long Mansion) - 原题 PDF 第 1 页
原题PDF第5页
細長い屋敷 (Long Mansion) - 原题 PDF 第 2 页
原题PDF第6页
細長い屋敷 (Long Mansion) - 原题 PDF 第 3 页
原题PDF第7页
細長い屋敷 (Long Mansion) - 原题 PDF 第 4 页
原题PDF第8页
可复制的 PDF 提取文本
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                                    Contest Day 3 – Long Mansion


               細長い屋敷(Long Mansion)



  JOI くんの家の近くには細長い屋敷がある.この屋敷は部屋が東西にN 個並んだ構造をしており,東か
らi 番目の部屋を部屋i と呼ぶ.部屋i と部屋i + 1 (1 ≦i ≦N −1) は廊下でつながっており,廊下は双方向
に通行可能である.部屋と廊下を行き来するためには鍵が必要である.鍵には種類と呼ばれる番号が付け
られている.同じ種類の鍵が複数あることもある.
 部屋i や部屋i + 1 から,部屋i と部屋i + 1 を結ぶ廊下に入るには,種類Ci の鍵が必要である.
 部屋i にはBi 個の鍵が落ちている.それらの鍵の種類はAi,j (1 ≦j ≦Bi) である.JOI くんは,部屋に入
るとその部屋に落ちている鍵を全て拾い,以後廊下に入るのに使うことができる.
 鍵は何度でも使うことができる.また,同じ鍵が複数手に入ることがあるが,1 つ持っているときと比
べて特別役に立つことはない.
  JOI くんは,この屋敷で迷子になったときに備えて,以下の形式のクエリに答えるプログラムを書くこ
とにした.

   • JOI くんが鍵を1 つも持っていない状態で部屋x に迷い込んだとき,部屋y に到達することはでき
   るか?

 あなたの仕事は,JOI くんに代わってこのクエリに答えるプログラムを書くことである.


課題

 屋敷の情報とクエリが与えられたとき,それぞれのクエリに対し,鍵を1 つも持っていない状態で部屋
に迷い込んだとき,部屋から部屋に到達することができるかを判定するプログラムを作成せよ.


入力

 標準入力から以下の入力を読み込め.

   • 1 行目には整数N が書かれている.これは屋敷には部屋がN 個あることを表す.

   • 2 行目にはN −1 個の整数C1,C2, . . . ,CN−1 が空白を区切りとして書かれている.これらは,部屋i や
   部屋i + 1 から,部屋i と部屋i + 1 を結ぶ廊下に入るには種類Ci の鍵が必要であることを表す.

   • 続くN 行のうちのi 行目(1 ≦i ≦N) には,1 以上の整数Bi と,Bi 個の整数Ai,1, Ai,2, . . . , Ai,Bi が空
   白を区切りとして書かれている.これは部屋i には鍵がBi 個落ちており,それらの鍵の種類がAi,j
      (1 ≦j ≦Bi) であることを表す.

   • 次の行には整数Q が書かれている.これはクエリがQ 個与えられることを表す.

   • 続くQ 行のうちのk 行目(1 ≦k ≦Q) には,2 個の整数Xk とYk が空白を区切りとして書かれている.
   これらは,k 番目のクエリが,鍵を1 つも持っていない状態で部屋Xk に迷い込んだとき,部屋Xk か
   ら部屋Yk に到達できるかを尋ねるものであることを表す.



                     細長い屋敷– 1 / 4

The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                                    Contest Day 3 – Long Mansion


出力

 標準出力にQ 行で出力せよ.Q 行のうちのk 行目(1 ≦k ≦Q) には,鍵を1 つも持っていない状態で部
屋Xk に迷い込んだとき,部屋Xk から部屋Yk に到達することができるならYES を,そうでないならNO を
出力せよ.


制限

 すべての入力データは以下の条件を満たす.

   • 2 ≦N ≦500 000.

   • 1 ≦Q ≦500 000.

   • 1 ≦B1 + B2 + · · · + BN ≦500 000.

   • 1 ≦Bi ≦N (1 ≦i ≦N).

   • 1 ≦Ci ≦N (1 ≦i ≦N −1).

   • 1 ≦Ai,j ≦N (1 ≦i ≦N, 1 ≦j ≦Bi).

   • Bi 個の整数Ai,1, . . . , Ai,Bi は互いに異なる(1 ≦i ≦N).

   • 1 ≦Xk ≦N (1 ≦k ≦Q).

   • 1 ≦Yk ≦N (1 ≦k ≦Q).

   • Xk , Yk (1 ≦k ≦Q).


小課題

 この課題では小課題は全部で4 個ある.各小課題の配点および追加の制限は以下の通りである.

小課題1 [5 点]

   • N ≦5 000.

   • Q ≦5 000.

   • B1 + B2 + · · · + BN ≦5 000.

小課題2 [5 点]

   • N ≦5 000.

   • B1 + B2 + · · · + BN ≦5 000.


                     細長い屋敷– 2 / 4

The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                                    Contest Day 3 – Long Mansion


小課題3 [15 点]

   • N ≦100 000.

   • Ci ≦20 (1 ≦i ≦N −1).

   •  Ai,j ≦20 (1 ≦i ≦N, 1 ≦j ≦Bi).

小課題4 [75 点]

 追加の制限はない.


入出力例

  入力例1        出力例1
   5                    YES
   1 2 3 4              NO
   2 2 3                NO
   1 1                  YES
   1 1
   1 3
   1 4
   4
   2 4
   4 2
   1 5
   5 3


   • 1 つ目のクエリでは,部屋2, 1, 2, 3, 4 の順に移動することで,部屋4 に到達することができる.

   • 2 つ目のクエリでは,部屋3, 4 にしか行くことができず,手に入れられる鍵の種類は1, 3 のみなので,
   部屋2 に到達することができない.

   • 3 つ目のクエリでは,部屋4 から部屋5 に行く種類4 の鍵を手に入れることができないため,部屋5
   に到達することができない.

   • 4 つ目のクエリでは,部屋5, 4, 3 の順に移動することで,部屋3 に到達することができる.





                     細長い屋敷– 3 / 4

The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                        Spring Training Camp/Qualifying Trial
                                           March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                                 Contest Day 3 – Long Mansion



入力例2        出力例2
5                    NO
2 3 1 3              YES
1 3                  NO
1 2                  YES
1 1
1 3
1 2
4
1 3
3 1
4 3
2 5

入力例3        出力例3
7                    YES
6 3 4 1 2 5          NO
1 1                  YES
1 5
1 1
1 1
2 2 3
1 4
1 6
3
4 1
5 3
4 7





                    細長い屋敷– 4 / 4