以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。






可复制的 PDF 提取文本
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail
刑務所(Jail)
IOI 刑務所は,JOI 国で最も厳重に管理された刑務所として知られている.この刑務所にはN 個の部屋
があり,1 からN までの番号が付けられている.また,この刑務所にはN −1 本の通路があり,i 番目
(1 ≦i ≦N −1) の通路は部屋Ai と部屋Bi を双方向に結んでいる.どの部屋からどの部屋へも,いくつかの
通路を通ることで移動することができる.
IOI 刑務所にはM 人の受刑者が収容されている.各受刑者には1 からM までの「称呼番号」が付けられ
ており,称呼番号j (1 ≦j ≦M) の受刑者の寝室は部屋S j,作業場所は部屋T j である.ある受刑者の寝室
が別の受刑者の作業場所に割り当てられていることはあるが,同じ部屋が複数の受刑者の寝室に割り当てら
れたり,同じ部屋が複数の受刑者の作業場所に割り当てられたりすることはない.
ある日の朝,M 人の受刑者全員を寝室から作業場所まで移動させることになった.IOI 刑務所の所長であ
るAPIO 氏は,以下の命令を繰り返すことで受刑者を移動させる.
命令受刑者を1 人選び,その受刑者を(現在いる部屋から)通路で直接結ばれている部屋に移動させる.
ただし,刑務所内での私語を防ぐため,移動先の部屋には他の受刑者がいてはならない.
刑務作業を早く始めるため,APIO 氏は,すべての受刑者が同じ部屋を二度通らずに最短経路で移動を完
了させることが可能かどうかを判定したい.
IOI 刑務所の部屋と通路の情報,受刑者の情報が与えられるので,すべての受刑者が最短経路で移動を完
了させることが可能かどうかを判定するプログラムを作成せよ.
刑務所– 1 / 6
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail
入力
1 つのテストケースはQ 個のシナリオからなり,シナリオには1 からQ までの番号が付けられている.
各シナリオに対して,以下の値が定められている.ただし,以下に記された値の範囲については,制約の項
を参照せよ.
• IOI 刑務所にある部屋の数N.
• IOI 刑務所の通路の情報(A1, B1), (A2, B2), · · · , (AN−1, BN−1).
• IOI 刑務所に収容されている受刑者の数M.
• 各受刑者の寝室と作業場所の部屋番号(S 1, T1), (S 2, T2), · · · , (S M, TM).
ここで,入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
Q
(シナリオ1 に対する入力)
(シナリオ2 に対する入力)
...
(シナリオQ に対する入力)
また,それぞれのシナリオに対する入力は,以下の形式で与えられる.詳しくは入出力例の項を参照せよ.
N
A1 B1
A2 B2
...
AN−1 BN−1
M
S 1 T1
S 2 T2
...
S M TM
刑務所– 2 / 6
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail
出力
標準出力にQ 行で出力せよ.k 行目(1 ≦k ≦Q) には,以下を出力せよ.
• シナリオk について,すべての受刑者を最短経路で移動させることが可能なときYes.
• シナリオk について,すべての受刑者を最短経路で移動させることが不可能なときNo.
制約
• 1 ≦Q ≦1 000.
• 2 ≦N ≦120 000.
• 1 ≦Ai < Bi ≦N (1 ≦i ≦N −1).
• 2 ≦M ≦N.
• 1 ≦S j ≦N (1 ≦j ≦M).
• 1 ≦T j ≦N (1 ≦j ≦M).
• S 1, S 2, · · · , S M は相異なる.
• T1, T2, · · · , TM は相異なる.
• S j , T j (1 ≦j ≦M).
• どの部屋からどの部屋へも,いくつかの通路を通ることで移動することができる.
• Q 個のシナリオにおけるN の値の合計は120 000 以下である.
小課題
1. (5 点) Ai = i,Bi = i + 1 (1 ≦i ≦N −1).
2. (5 点) Q ≦20,N ≦250,M = 2.
3. (16 点) Q ≦20,N ≦250,M ≦6.
4. (28 点) Q ≦20,N ≦250,M ≦100.
5. (12 点) Q ≦20,M ≦500.
6. (11 点) どの部屋からどの部屋へも,高々20 本の通路を使って移動することができる.
7. (23 点) 追加の制約はない.
刑務所– 3 / 6
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail
入出力例
入力例1 出力例1
1 Yes
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
2
3 4
4 8
この入力例では,次のような手順で命令を出すことにより,すべての受刑者を最短経路で移動させること
ができる.
1. 称呼番号2 の受刑者を,部屋4 から部屋5 に移動させる.
2. 称呼番号1 の受刑者を,部屋3 から部屋4 に移動させる.
3. 称呼番号2 の受刑者を,部屋5 から部屋6 に移動させる.
4. 称呼番号2 の受刑者を,部屋6 から部屋7 に移動させる.
5. 称呼番号2 の受刑者を,部屋7 から部屋8 に移動させる.
したがって,Yes を出力する.なお,この入力例における刑務所の構造は以下の図のようになっている.
この入力例はすべての小課題の制約を満たす.
1 3 5 7
2 4 6 8
刑務所– 4 / 6
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail
入力例2 出力例2
2 Yes
7 No
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
4
1 2
1 3
1 4
3
2 3
3 4
4 2
この入力例はQ = 2 個のシナリオからなる.シナリオ1 では,次のような手順で命令を出すことにより,
すべての受刑者を最短経路で移動させることができる.
1. 称呼番号1 の受刑者を,部屋4 から部屋3 に移動させる.
2. 称呼番号1 の受刑者を,部屋3 から部屋2 に移動させる.
3. 称呼番号2 の受刑者を,部屋5 から部屋4 に移動させる.
4. 称呼番号2 の受刑者を,部屋4 から部屋3 に移動させる.
5. 称呼番号2 の受刑者を,部屋3 から部屋6 に移動させる.
6. 称呼番号1 の受刑者を,部屋2 から部屋1 に移動させる.
7. 称呼番号2 の受刑者を,部屋6 から部屋7 に移動させる.
一方,シナリオ2 では,すべての受刑者を最短経路で移動させることはできない.したがって,1 行目に
はYes,2 行目にはNo を出力する.
この入力例は小課題3, 4, 5, 6, 7 の制約を満たす.
刑務所– 5 / 6
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail
入力例3 出力例3
3 Yes
3 No
1 2 Yes
2 3
2
2 1
3 2
7
1 2
2 3
3 4
4 5
5 6
6 7
3
1 3
4 2
2 5
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 5
2 6
3 7
4 8
この入力例は小課題1, 3, 4, 5, 6, 7 の制約を満たす.
刑務所– 6 / 6