C - ボードゲーム (Board Game) 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

K 人用のボードゲームがある.このボードゲームのボードには 1 から N までの番号のついた N 個のマスと,1 から M までの番号のついた M 本の道があり,道 j (1 \leqq j \leqq M) はマス U_j と V_j の間を双方向に接続している.

N 個のマスには 再行動マス と 停止マス との 2 種類がある.その情報は 0, 1 からなる長さ N の文字列 S によって与えられ,S の i 文字目 (1 \leqq i \leqq N) が 0 ならばマス i は再行動マス,S の i 文字目が 1 ならばマス i は停止マスである.

このボードゲームは 1 から K までの番号がついた K 人のプレイヤーで遊ぶ.各プレイヤーは自分の駒を 1 つ持っており,各プレイヤーの駒を指定されたマスの上に置いてゲームを開始する.はじめプレイヤー p (1 \leqq p \leqq K) の駒はマス X_p に置く.なお,1 つのマスに複数のプレイヤーの駒を置くことも可能である.

ゲームはプレイヤー 1 から始めて番号順に自分のターンをプレイするという形で進行する.プレイヤー p が自分のターンをプレイし終わると,次はプレイヤー p+1(ただし p=K ならばプレイヤー 1)のターンとなる.各プレイヤーは,自分のターンのときに次のような行動を行う:

  1. 自分の駒が置かれているマスと道で接続されているマスをひとつ選び,選んだマスに自分の駒を移動させる.
  2. 移動先のマスが再行動マスならば 1. に戻り,自分のターンを継続する.移動先のマスが停止マスならば自分のターンを終了する.

このボードゲームの日本代表である JOI 君たち K 人は,ゲームを協力して高速に攻略する方法を研究している.現在研究しているのは次の問題である:

プレイヤー 1 の駒がマス T に置かれている状態にするために必要な,K 人合計での駒の移動回数の最小値はいくつか.なお,ターンの途中であっても,プレイヤー 1 の駒がマス T に置かれれば条件が満たされたものとみなす.

ボードゲームのボードの情報と各プレイヤーの駒の初期配置が与えられた場合に,各 T=1,2,\ldots,N に対して,この問題の答えを計算するプログラムを作成せよ.


入力

入力は以下の形式で標準入力から与えられる.

N M K
U_1 V_1
U_2 V_2
\vdots
U_M V_M
S
X_1 X_2 \cdots X_K

出力

標準出力に N 行出力せよ.T 行目 (1 \leqq T \leqq N) には,プレイヤー 1 の駒がマス T に置かれている状態にするために必要な,K 人合計での駒の移動回数の最小値を出力せよ.


制約

  • 2 \leqq N \leqq 50\,000.
  • 1 \leqq M \leqq 50\,000.
  • 2 \leqq K \leqq 50\,000.
  • 1 \leqq U_j < V_j \leqq N (1 \leqq j \leqq M).
  • (U_j,V_j) \neq (U_k,V_k) (1 \leqq j < k \leqq M).
  • どのマスからどのマスへも,結ばれている道を何本か辿って到達できる.
  • S は 0, 1 からなる長さ N の文字列である.
  • 1 \leqq X_p \leqq N (1 \leqq p \leqq K).
  • N,M,K は整数である.
  • U_j,V_j は整数である (1 \leqq j \leqq M).
  • X_p は整数である (1 \leqq p \leqq K).

小課題

  1. (7 点) 停止マスは存在しない.
  2. (12 点) 停止マスの個数は 1 個である.
  3. (12 点) 停止マスの個数は 2 個である.
  4. (23 点) N \leqq 3\,000,M \leqq 3\,000,K \leqq 3\,000.
  5. (23 点) K=2.
  6. (7 点) K \leqq 100.
  7. (12 点) N \leqq 30\,000,M \leqq 30\,000,K \leqq 30\,000.
  8. (4 点) 追加の制約はない.

入力例 1

5 5 2
1 2
2 3
2 4
3 5
4 5
00000
1 5

出力例 1

0
1
2
2
3

はじめプレイヤー 1 の駒はマス 1 に置かれているので,T=1 に対する答えは 0 である.

T=2 のとき,1 回目の移動で,プレイヤー 1 の駒をマス 1 からマス 2 に移動させることができる.したがって T=2 に対する答えは 1 である.

T=3 のとき,次のような 2 回の移動でプレイヤー 1 の駒をマス 3 に置くことができる.

  • 1 回目の移動では,プレイヤー 1 の駒をマス 1 からマス 2 に移動させる.マス 2 は再行動マスであるから,プレイヤー 1 のターンが継続される.
  • 2 回目の移動では,プレイヤー 1 の駒をマス 2 からマス 3 に移動させる.

1 回以下の移動でプレイヤー 1 の駒をマス 3 に置くことはできないため,T=3 に対する答えは 2 である.

同様に T=4 に対する答えは 2,T=5 に対する答えは 3 であることが確かめられる.

この入力例は小課題 1,4,5,6,7,8 の制約を満たす.


入力例 2

5 5 2
1 2
2 3
2 4
3 5
4 5
01000
1 5

出力例 2

0
1
4
4
5

例えば T=3 のとき,次のような 4 回の移動でプレイヤー 1 の駒をマス 3 に置くことができる.

  • 1 回目の移動では,プレイヤー 1 の駒をマス 1 からマス 2 に移動させる.マス 2 は停止マスであるから,次はプレイヤー 2 のターンとなる.
  • 2 回目の移動では,プレイヤー 2 の駒をマス 5 からマス 3 に移動させる.マス 3 は再行動マスであるから,プレイヤー 2 のターンが継続される.
  • 3 回目の移動では,プレイヤー 2 の駒をマス 3 からマス 2 に移動させる.マス 2 は停止マスであるから,次はプレイヤー 1 のターンとなる.
  • 4 回目の移動では,プレイヤー 1 の駒をマス 2 からマス 3 に移動させる.

3 回以下の移動でプレイヤー 1 の駒をマス 3 に置くことはできないため,T=3 に対する答えは 4 である.

この入力例は小課題 2,4,5,6,7,8 の制約を満たす.


入力例 3

5 5 2
1 2
2 3
2 4
3 5
4 5
01100
1 5

出力例 3

0
1
3
3
4

この入力例は小課題 3,4,5,6,7,8 の制約を満たす.


入力例 4

8 7 5
1 3
5 7
4 6
2 6
2 3
7 8
1 5
10011010
4 6 4 7 1

出力例 4

4
2
3
0
10
1
17
24

この入力例は小課題 4,6,7,8 の制約を満たす.


入力例 5

12 13 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
2 9
7 12
11 12
110000011101
1 9 11

出力例 5

0
1
4
5
6
7
8
8
4
1
13
9

この入力例は小課題 4,6,7,8 の制約を満たす.


出典

JOIG 2023/2024 春季トレーニング Contest Day1