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




可复制的 PDF 提取文本
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Bitaro’s Party
ビ太郎のパーティー(Bitaro’s Party)
ビーバーが住んでいる町がN 個あり,標高が高い順に町1 から町N までの番号が付けられている.同じ
標高の町は無い.異なる町を結ぶ一方向に流れる水路がM 本存在している.i 番目の水路(1 ≦i ≦M) は,
町S i から町Ei に流れている.これらの水路は,標高が高い町から低い町へ一方向に流れている.流れに
逆らって水路を移動することはできない.
ビーバーのビ太郎には,N 人の友人がおり,N 個の町それぞれに1 人ずつ住んでいる.
ビ太郎は,友人を招待してパーティーをQ 回開こうと考えている.j 番目(1 ≦j ≦Q) のパーティーに
は,Y j 人の友人は都合が悪く,参加できないことが分かっている.また,j 番目のパーティーは町T j で開
催されるので,水路だけで町T j まで到達することができない友人も,j 番目のパーティーに参加できない.
それ以外の友人は,パーティーに参加する.
それぞれの友人は,水路を経由してパーティーの開催される町まで移動する.移動する経路が複数存在
するかもしれない.ただし,ビ太郎の友人は水路が好きなので,複数の経路がある場合は,経由する水路
の本数が最も多くなるような経路のいずれかで移動することが分かっている.
ビ太郎は,それぞれのパーティーについて,最も多くの水路を経由する参加者が,何本の水路を経由す
るかが気になった.
課題
Q 回のパーティーそれぞれについて,開催される町の番号と都合の悪い友人の一覧が与えられたとき,
最も多くの水路を経由する参加者が,何本の水路を経由するかを出力するプログラムを作成せよ.
ビ太郎のパーティー– 1 / 4
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Bitaro’s Party
入力
標準入力から以下の入力を読み込め.
• 1 行目には,3 個の整数N, M, Q が空白を区切りとして書かれている.これは,町がN 個あり,水路
がM 本存在し,ビ太郎がQ 回のパーティーを開くことを表す.
• 続くM 行には,水路の情報が書かれている.M 行のうちのi 行目(1 ≦i ≦M) には,整数S i, Ei が空
白を区切りとして書かれており,町S i から町Ei に一方向の水路が流れていることを表す.
• 続くQ 行には,ビ太郎が開くパーティーの情報が書かれている.Q 行のうちのj 行目(1 ≦j ≦Q) に
は,整数T j, Y j およびY j 個の整数C j,1,C j,2, . . . ,C j,Yj が空白を区切りとして書かれている.これは,
j 番目のパーティーは町T j で開催され,町C j,1,C j,2, . . . ,C j,Yj に住んでいる友人の都合が悪いことを
表す.
出力
出力はQ 行からなる.j 行目(1 ≦j ≦Q) には,j 番目のパーティーにおいて,最も多くの水路を経由す
る参加者が,何本の水路を経由するかを出力せよ.ただし,パーティーに友人が一人も参加することがで
きない場合は,代わりに-1 を出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 1 ≦N ≦100 000.
• 0 ≦M ≦200 000.
• 1 ≦Q ≦100 000.
• 1 ≦S i < Ei ≦N (1 ≦i ≦M).
• (S i, Ei) , (S j, E j) (1 ≦i < j ≦M).
• 1 ≦T j ≦N (1 ≦j ≦Q).
• 0 ≦Y j ≦N (1 ≦j ≦Q).
• 1 ≦C j,1 < C j,2 < · · · < C j,Yj ≦N (1 ≦j ≦Q).
• Y1 + Y2 + · · · + YQ ≦100 000.
ビ太郎のパーティー– 2 / 4
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Bitaro’s Party
小課題
この課題では小課題は全部で3 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [7 点]
• N ≦1 000.
• M ≦2 000.
• Q = 1.
小課題2 [7 点]
• Q = 1.
小課題3 [86 点]
追加の制限はない.
入出力例
入力例1 出力例1
5 6 3 1
1 2 3
2 4 0
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5
1 番目のパーティーに参加する友人(町2,3,4 に住む友人) の中では,町2 に住む友人と町3 に住む友
人が,パーティーが開催される町4 に移動するのに経由する水路の本数が最も多い.この本数は,1 本で
あるので,1 を出力する.
2 番目のパーティーに参加する友人(町1,4,5 に住む友人) の中では,町1 に住む友人が,パーティー
が開催される町5 に移動するのに経由する水路の本数が最も多い.この本数は,3 本であるので,3 を出
力する.
3 番目のパーティーに参加する友人は,パーティーの開催される町2 に住む友人のみである.この友人
は水路を経由しないので,0 を出力する.
ビ太郎のパーティー– 3 / 4
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Bitaro’s Party
入力例2 出力例2
12 17 10 1
1 2 -1
2 3 3
3 4 1
1 5 3
2 6 -1
3 7 5
4 8 2
5 6 4
6 7 4
7 8
5 9
6 10
7 11
8 12
9 10
10 11
11 12
6 3 1 7 12
3 7 1 2 3 4 5 6 7
11 3 1 3 5
9 2 1 9
8 4 1 2 3 4
1 1 1
12 0
10 3 1 6 10
11 8 2 3 5 6 7 9 10 11
8 7 2 3 4 5 6 7 8
ビ太郎のパーティー– 4 / 4