AT_hokudai_hitachi2019_2_a Problem C

[problemUrl]: https://atcoder.jp/contests/hokudai-hitachi2019-2/tasks/hokudai_hitachi2019_2_a

N/A

N/A

### 時間・空間について - **時間**: $ t $ は $ 0\ \leq\ t\ $ \mathrm{verdict} $ $ N_{\text{achieve}} $ $ \mathrm{achieve\_id}_1 $ $ \mathrm{achieve\_id}_2 $ $ \vdots $ $ \mathrm{achieve\_id}_{N_{\text{achieve}}} $ - $ \mathrm{verdict} $ は、時刻 $ t $ における車の行動が実行可能であるかを表す文字列であり、以下の $ 4 $ 種類のいずれかである。 - `OK`: 行動は実行可能であり、車は行動に従って動く(もしくはとどまる)ことを表す。 - `NG`: 行動は実行不可能であり、`NG` が出力された場合、コンテスタントはプログラムを即座に終了させなければならない。即座に終了させた場合は `WA` (不正解) となることが保証されるが、そうでない場合の動作は未定義である。 - `JAM`: 渋滞によって車が進めなかったことを表す。(渋滞方向への移動であっても、車が進めれば `OK` が出力される) - `WAIT t`: 行動は実行可能であり、車が所望の頂点に移動したことを表す。ただし、赤信号のため次の $ t $ ステップの間、その場にとどまらなくてはならない。その間、コンテスタントコードは `-1` を出力しなければならない。 `-1` を出力しなければ `NG` となる。なお、信号待ちに該当する頂点に移動した場合であっても、青信号であれば `OK` が出力される。 - $ N_{\text{achieve}} $ は、その時刻において配達が完了した注文の数を表す。 - その時点で車が店にいなければ、$ N_{\text{achieve}} $ は $ 0 $ である。 - 続く $ N_{\text{achieve}} $ 行で、配達が完了した注文情報が与えられる。$ i $ 行目の注文情報は、注文 ID が $ \mathrm{achieve\_id}_i $ であることを表す。 また、$ T_{\max} $ 回目の行動に対するジャッジからの入力を受け取ったあと、あなたは **プログラムを即座に終了させなければならない。** ### 入出力制約 - 入力で与えられる数値はすべて整数である - 出力はすべて整数でなければならない #### 初期化 - $ T_{\text{max}}\ =\ 10000 $ - $ |V|\ =\ 625 $ - $ 1.5\ |V|\ \leq\ |E|\ \leq\ 2|V| $ - $ 1\ \leq\ u_{i},\ v_{i}\ \leq\ |V| $ $ (1\ \leq\ i\ \leq\ |E|) $ - $ 1\ \leq\ d_{u_i,\ v_i}\ \leq\ \lceil\ 4\sqrt{2|V|}\ \rceil $ $ (1\ \leq\ i\ \leq\ |E|) $ - $ 0\ \leq\ e_{u_i,\ v_i},\ e_{v_i,\ u_i}\ \leq\ 6 $ $ (1\ \leq\ i\ \leq\ |E|) $ - 与えられるグラフは自己ループ・多重辺が存在せず、連結であることが保証される - $ f_1\ =\ 0 $ - $ f_i\ \in\ \left\{0,\ 1,\ 2\ \right\} $ ($ 2\ \leq\ i\ \leq\ |V| $) - $ 0\ \leq\ t_{d,1}\ \leq\ t_{d,2}\ \leq\ t_{d,3}\ \leq\ t_{d,4}\ \lt\ T_{\text{max}} $ $ (1\ \leq\ d\ \leq\ 4) $ - $ 50\ \leq\ T_{\text{warning}}\ \leq\ 120 $ - $ 10\ \leq\ P_{\text{light}}\ \leq\ 30 $ #### 繰り返し処理 - $ \mathrm{CAR\_STATUS}\ \in $ $ \{ $ `NOT_BROKEN`, `WARNING t`, `BROKEN`$ \} $ - $ \mathrm{jam}_{1},\ \mathrm{jam}_{2},\ \mathrm{jam}_{3},\ \mathrm{jam}_{4}\ \in\ \{0,1\} $ - $ 0\ \leq\ N_{\text{new}}\ \leq\ 1 $ - $ 1\ \leq\ \mathrm{new\_id}_{i}\ \leq\ T_{\text{last}}+1 $ $ (1\ \leq\ i\ \leq\ N_{\text{new}}) $. 注意: 上で説明されたルールに従って注文が生成されたとき、発生する注文の件数の最大値は $ T_{\text{last}}\ +\ 1 $ となる。ゆえに、$ \mathrm{new\_id}_{i} $ の取りうる値は $ 1 $ から $ T_{\text{last}}\ +\ 1 $ までの整数である。 - ジャッジからの出力全体を通して、注文ID $ \mathrm{new\_{id}}_i $ はそれぞれ相異なる整数である - $ 2\ \leq\ \mathrm{dst}_i\ \leq\ |V| $ $ (1\ \leq\ i\ \leq\ N_{\text{new}}) $ - $ 0\ \leq\ N_{\text{cancel}}\ \leq\ T_{\text{last}}+1 $ - $ 1\ \leq\ \mathrm{cancel\_id}_{i}\ \leq\ T_{\text{last}}+1 $ $ (1\ \leq\ i\ \leq\ N_{\text{cancel}}) $. - $ 0\ \leq\ N_{\text{put}}\ \leq\ T_{\text{last}}+1 $ - $ 1\ \leq\ \mathrm{put\_id}_{i}\ \leq\ T_{\text{last}}+1 $ $ (1\ \leq\ i\ \leq\ N_{\text{put}}) $. - 時刻 $ t $ におけるあなたの行動を表す整数は $ -1 $ または $ 1\ \leq\ w\ \leq\ |V| $ を満たす整数 $ w $ でなければならない - $ \mathrm{verdict}\ \in\ \{ $`OK`, `NG`,`JAM`, `WAIT t`$ \} $ - $ 0\ \leq\ N_{\text{achieve}}\ \leq\ T_{\text{last}}+1 $ - $ 1\ \leq\ \mathrm{achieve\_id}_{i}\ \leq\ T_{\text{last}}+1 $ $ (1\ \leq\ i\ \leq\ N_{\text{achieve}}) $. - - - - - - ### 入出力例 以下では入出力例を用いて、コンテスタント側とジャッジ側の挙動を説明する。 - **グラフ** : 以下では $ 16 $ 頂点、 $ 18 $ つの辺をもつグラフを例として挙げる。 - **スピードウェイ**: 下図の黒い頂点で表す。以下のように $ 4 $ つの方向がある。 - $ d=1 $ : $ 3\to7\to11\to15 $ - $ d=2 $ : $ 15\to11\to7\to3 $ - $ d=3 $ : $ 9\to10\to11\to12 $ - $ d=4 $ : $ 12\to11\to10\to9 $. - 時間ステップ $ 0 $ から $ 8 $ : 車は頂点 $ 14 $ を訪問し、注文(ID: $ 1 $) の配達を行う。この間、頂点 $ 16 $ で発生した注文がキャンセルされる。配達経路を赤い矢印で示す。渋滞によりステップ $ 4 $ から $ 5 $ の間、車は動けない。 - 時間ステップ $ 8 $ から $ 14 $ : 車の故障警告 `WARNING 5` が発生し、修理のため車は店(頂点 $ 1 $ )を目指す。しかし、頂点 $ 9 $ で信号待ち( `WAIT 2` )が発生し、ステップ $ 11,\ 12 $ で車は動けない。 - 時間ステップ $ 13 $ で頂点 $ 1,\ 9 $ の間で車が故障し、`BROKEN` の通知を受け取る。 - 時間ステップ $ 14 $ :車の故障中に実行不可能な行動を行ったため、`NG` が出力される。  注意: この例はわかりやすさのために作られたものであり、制約条件は満たさない。 時間 コンテスタント ジャッジ 説明 ```

16 18
5 1 2 0 0
2 3 2 5 6
2 6 4 0 0
3 4 2 6 5
3 7 1 1 2
4 8 4 0 0
1 6 2 0 0
1 9 2 5 6
7 11 1 1 2
9 10 1 3 4
9 13 2 6 5
9 14 2 6 5
10 11 1 3 4
11 12 1 3 4
11 15 1 1 2
12 16 2 6 5
14 15 2 5 6
15 16 2 6 5
0 1 0 1 1 2 0 1 0 0 0 0 1 1 0 1
3 167 311 913
63 617 791 837
325 473 893 915
156 387 627 849
6
5
10000
```

  はじめに、ジャッジ側からデータが与えられる   
 $ 1 $ 行目: グラフは $ |V|\ =\ 16 $ 個の頂点と $ |E|\ =\ 18 $ つの辺から構成される   
 次の $ 18 $ 行 (行 $ 2 $ - $ 19 $) は、グラフの辺に関する情報を表す。例えば、   
 $ 2 $ 行目: 頂点 $ 5 $ と頂点 $ 1 $ の間の距離が $ 2 $ で、$ 4 $ 番目の数字 $ 0 $ は、$ 5\to\ 1 $ 方向の道が通常の道であることを示し、最後の $ 0 $ は $ 1\to\ 5 $ 方向の道も通常の道であることを示す   
 $ 3 $ 行目: 頂点 $ 2 $ と頂点 $ 3 $ の間の距離が $ 2 $ で、$ 4 $ 番目の数字 $ 5 $ は、$ 2\to\ 3 $ の方向に進むと通常の道からスピードウェイに入ることを示し、最後の $ 6 $ は $ 3\to\ 2 $ 方向に進むとスピードウェイから通常の道に戻ることを示す   
 $ 6 $ 行目: 頂点 $ 3 $ と頂点 $ 7 $ の間の距離が $ 1 $ で、$ 4 $ 番目の数字 $ 1 $ は、$ 3\to\ 7 $ の方向がスピードウェイの方向 $ d=1 $ に対応することを示し、最後の $ 2 $ は $ 7\to\ 3 $ の方向がスピードウェイの方向 $ d=2 $ に対応することを示す   
 $ 20 $ 行目: 各頂点における注文発生頻度を示す   
 $ 21 $ 行目: 方向 $ d=1 $ の渋滞開始時刻の目安($ i=1,...,4 $)を示す   
 $ 22 $ 行目: 方向 $ d=2 $ の渋滞開始時刻の目安($ i=1,...,4 $)を示す   
 $ 23 $ 行目: 方向 $ d=3 $ の渋滞開始時刻の目安($ i=1,...,4 $)を示す   
 $ 24 $ 行目: 方向 $ d=4 $ の渋滞開始時刻の目安($ i=1,...,4 $)を示す   
 $ 25 $ 行目: 信号の周期 $ P_{\text{light}}=6 $ を示す   
 $ 26 $ 行目: 車の故障警告期間 $ T_{\text{warning}}=5 $ を示す   
 $ 27 $ 行目: 時間ステップの最大値 $ T_{\max}=10000 $ を示す  $ 0\ \rightarrow\ 1 $   ```
NOT_BROKEN
0 0 0 0
0
1
1 14
1
1
```

   時刻 $ t=0 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)   
 $ 2 $ 行目: 渋滞は発生していない   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに $ 1 $ つの注文があった   
 $ 5 $ 行目: 新規注文のIDは $ 1 $ であり、届け先は頂点 $ 14 $ である   
 $ 6 $ 行目: 車は店に居るので、 $ 1 $ つの注文に対応する荷物を車に積んだ   
 $ 7 $ 行目: 荷物に対応する注文IDは $ 1 $ である   ```
9
```

    コンテスタントは車を頂点 $ 9 $ に向けて距離 $ 1 $ だけ進める    ```
OK
0
```

   最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す  $ 1\ \rightarrow\ 2 $   ```
NOT_BROKEN
0 0 0 0
0
1
2 16
0
```

   時刻 $ t=1 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)   
 $ 2 $ 行目: 渋滞は発生していない   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに $ 1 $ つの注文があった   
 $ 5 $ 行目: 新規注文のIDは $ 2 $ であり、届け先は頂点 $ 16 $ である   
 $ 6 $ 行目: 車は店に居ないので、荷物は車に積まれなかった   ```
9
```

    コンテスタントは車を頂点 $ 9 $ に向けて距離 $ 1 $ だけ進める    ```
OK
0
```

   車はスピードウェイに入った。このとき信号は青である。したがって、最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す  $ 2\ \rightarrow\ 3 $   ```
NOT_BROKEN
0 0 0 0
0
0
0
```

   時刻 $ t=2 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)   
 $ 2 $ 行目: 渋滞は発生していない   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 5 $ 行目: 荷物は車に積まれなかった   ```
10
```

    コンテスタントは車を頂点 $ 10 $ に向けて距離 $ 1 $ だけ進める    ```
OK
0
```

   最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す  $ 3\ \rightarrow\ 4 $   ```
NOT_BROKEN
0 0 0 0
0
0
0
```

   時刻 $ t=3 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)   
 $ 2 $ 行目: 渋滞は発生していない   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 5 $ 行目: 荷物は車に積まれなかった   ```
11
```

    コンテスタントは車を頂点 $ 11 $ に向けて距離 $ 1 $ だけ進める    ```
OK
0
```

   最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す  $ 4\ \rightarrow\ 5 $   ```
NOT_BROKEN
1 0 0 0
0
0
0
```

   時刻 $ t=4 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)   
 $ 2 $ 行目: 渋滞がスピードウェイの方向 $ d=1 $ で発生している   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 5 $ 行目: 荷物は車に積まれなかった   ```
15
```

    コンテスタントは車を頂点 $ 15 $ に向けて距離 $ 1 $ だけ進めようとする    ```
JAM
0
```

   最初の行は車が渋滞により進めなかったことを示す。そのため、車は頂点 $ 11 $ にとどまる。$ 2 $ 行目は配達が行われなかったことを表す  $ 5\ \rightarrow\ 6 $   ```
NOT_BROKEN
1 0 0 0
0
0
0
```

   時刻 $ t=5 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)   
 $ 2 $ 行目: 渋滞がスピードウェイの方向 $ d=1 $ で発生している   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 5 $ 行目: 荷物は車に積まれなかった   ```
15
```

    コンテスタントは車を頂点 $ 15 $ に向けて距離 $ 1 $ だけ進めようとする (依然としてこの方向には渋滞が発生している)    ```
OK
0
```

   最初の行は車が運良く進めたことを示す。$ 2 $ 行目は配達が行われなかったことを表す  $ 6\ \rightarrow\ 7 $   ```
NOT_BROKEN
1 0 0 0
0
0
0
```

   時刻 $ t=6 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)   
 $ 2 $ 行目: 渋滞がスピードウェイの方向 $ d=1 $ で発生している   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 5 $ 行目: 荷物は車に積まれなかった   ```
14
```

    コンテスタントは車を頂点 $ 14 $ に向けて距離 $ 1 $ だけ進める    ```
OK
0
```

   最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す  $ 7\ \rightarrow\ 8 $   ```
NOT_BROKEN
0 0 0 0
1
2
0
0
```

   時刻 $ t=7 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)   
 $ 2 $ 行目: 渋滞は発生していない   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 1 $ である   
 $ 4 $ 行目: キャンセルされた注文のIDは $ 2 $ である   
 $ 5 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 6 $ 行目: 荷物は車に積まれなかった   ```
14
```

    コンテスタントは車を頂点 $ 14 $ に向けて距離 $ 1 $ だけ進める    ```
OK
1
1
```

   最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は $ 1 $ つの注文が配達されたことを示す。$ 3 $ 行目は配達された注文のIDが $ 1 $ であることを示す  $ 8\ \rightarrow\ 9 $   ```
WARNING 5
0 0 0 0
0
0
0
```

   時刻 $ t=8 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は故障警告状態であり、あと $ 5 $ ステップで故障する (`WARNING 5`)   
 $ 2 $ 行目: 渋滞は発生していない   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 5 $ 行目: 荷物は車に積まれなかった   ```
9
```

    コンテスタントは車を頂点 $ 9 $ に向けて距離 $ 1 $ だけ進める    ```
OK
0
```

   最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す  $ 9\ \rightarrow\ 10 $   ```
WARNING 4
0 0 0 0
0
0
0
```

   時刻 $ t=9 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は故障警告状態であり、あと $ 4 $ ステップで故障する (`WARNING 4`)   
 $ 2 $ 行目: 渋滞は発生していない   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 5 $ 行目: 荷物は車に積まれなかった   ```
9
```

    コンテスタントは車を頂点 $ 9 $ に向けて距離 $ 1 $ だけ進める    ```
WAIT 2
0
```

   最初の行は車の行動が実行可能であることを示す。したがって車はスピードウェイ上の頂点 $ 9 $ に到達する。しかし赤信号のため、 $ 2 $ ステップの間、車は現在の頂点にとどまらなければならない。$ 2 $ 行目は配達が行われなかったことを表す  $ 10\ \rightarrow\ 11 $   ```
WARNING 3
0 0 0 0
0
0
0
```

   時刻 $ t=10 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は故障警告状態であり、あと $ 3 $ ステップで故障する (`WARNING 3`)   
 $ 2 $ 行目: 渋滞は発生していない   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 5 $ 行目: 荷物は車に積まれなかった   ```
-1
```

    赤信号のため、コンテスタントは頂点 $ 9 $ に車をとどめなくてはならない (とどめなかった場合、 `NG` となる)    ```
WAIT 1
0
```

   最初の行は車の行動が実行可能であることを示す。しかし赤信号のため、$ 1 $ ステップの間、車は現在の頂点にとどまらなければならない。$ 2 $ 行目は配達が行われなかったことを表す  $ 11\ \rightarrow\ 12 $   ```
WARNING 2
0 0 0 0
0
0
0
```

   時刻 $ t=11 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は故障警告状態であり、あと $ 2 $ ステップで故障する (`WARNING 2`)   
 $ 2 $ 行目: 渋滞は発生していない   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 5 $ 行目: 荷物は車に積まれなかった   ```
-1
```

   赤信号のため、コンテスタントは頂点 $ 9 $ に車をとどめなくてはならない (とどめなかった場合、 `NG` となる)   ```
OK
0
```

   最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す  $ 12\ \rightarrow\ 13 $   ```
WARNING 1
0 0 0 0
0
0
0
```

   時刻 $ t=12 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は故障警告状態であり、あと $ 1 $ ステップで故障する (`WARNING 1`)   
 $ 2 $ 行目: 渋滞は発生していない   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 5 $ 行目: 荷物は車に積まれなかった   ```
1
```

    コンテスタントは車を頂点 $ 1 $ に向けて距離 $ 1 $ だけ進める (信号待ちは終了)    ```
OK
0
```

   最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す  $ 13\ \rightarrow\ 14 $   ```
BROKEN
0 0 0 0
0
0
0
```

   時刻 $ t=13 $ で以下の情報が与えられる:   
 $ 1 $ 行目: 車は故障状態となった。(`BROKEN`) (コンテスタントは行動 `-1` を出力しなければならない)   
 $ 2 $ 行目: 渋滞は発生していない   
 $ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である   
 $ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である   
 $ 5 $ 行目: 荷物は車に積まれなかった   ```
1
```

    コンテスタントは車を頂点 $ 1 $ に向けて距離 $ 1 $ だけ進めようとする    ```
NG
```

   最初の行は車の行動が実行不可能であることを示す(車が故障中にも関わらず動かそうとしたため)。コンテスタントはプログラムを終了させなければならない。(もしコンテスタントが一つ前のステップで車を店に戻せていたら、車は修理され、車の状態は正常状態 `NOT_BROKEN` となっていた)。$ 2 $ 行目は配達が行われなかったことを表す ### 出力の flush について

この問題では出力を flush する必要がある。例として、主要言語において `-1` と出力して flush する例は以下の通りである。

#### C++

 ```
std::cout 

Java
System.out.println("-1");

Python 3.4
print("-1", flush=True)

```

### サンプルコード C

この問題について、以下のツールキット一式は[ここ](https://img.atcoder.jp/hokudai-hitachi2019-2/2feac369fc0c9ac899efd364b4714c14.zip)からダウンロードできます。

- 入力サンプルジェネレータ
- テスター

また、ビシュアライザも[ここ](https://img.atcoder.jp/hokudai-hitachi2019-2/cb1bbbd4fef5d202b3707dcee0212d37.zip)にご用意しております。