IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
5 . 高速公鹿
TopCoder
Tags
Description
日野動物園特有的鹿鹿大遊行
由於日野動物園腹地廣大，園方正考慮將「鹿鹿大遊行」作為一種交通方式，讓旅客搭乘鹿在園區內不同的區域之間移動。
日野動物園內一共有 $N$ 個不同的區域，區域以 $1$ 到 $N$ 的整數編號，其中第 $1$ 個區域為園區入口，而第 $N$ 個區域是最熱門的區域——鹿園。日野動物園每天一共有 $M$ 場鹿鹿大遊行，園方將每天的營業時間分成 $10 ^ 9$ 等分，開園時為時間 $1$，閉園時為時間 $10 ^ 9$。第 $i$ 場的鹿鹿大遊行將在時間 $s_i$ 從區域 $u_i$ 開始，並在時間 $t_i$ 抵達區域 $v_i$。
由於大部分的旅客在進入園區後都直接前往鹿園，因此日野動物園評估路線的方式為：開園時從園區入口開始，搭乘鹿鹿大遊行最快能在哪個時間點抵達鹿園。旅客只能透過鹿鹿大遊行移動，在沒有搭乘鹿鹿大遊行時必須停在原本所在的區域。如果要搭乘鹿鹿大遊行，旅客必須在鹿鹿大遊行開始的時間點或開始之前抵達該區域。
最近園方打算更動鹿鹿大遊行的行程，他們列出了 $Q$ 個更改的方式。每一個方式可能是以下的其中一種：
- $1\ i\ s_i'\ t_i'$：表示第 $i$ 場的鹿鹿大遊行被改為從時間 $s_i'$ 開始，並會在時間 $t_i'$ 抵達目的地。
- $2\ i$：取消第 $i$ 場的鹿鹿大遊行。
- $3\ u'\ v'\ s'\ t'$：新增一場鹿鹿大遊行在時間 $s'$ 從區域 $u'$ 開始，並在時間 $t'$ 抵達區域 $v'$。
日野動物園想知道，鹿鹿大遊行的行程在分別經過這些修改的方式後，開園時透過鹿鹿大遊行從園區入口到鹿園需要花多少時間。注意 $Q$ 個更改的方式之間是沒有關聯的，也就是說，園方想知道的是，對於每一個更改的方式，用原本的行程進行該更改後，最快能抵達鹿園的時間。你能寫一支程式幫助日野動物園嗎？
Input Format
輸入的第一行包含兩個整數 $N,M$。接下來 $M$ 行，每行包含四個整數 $u_i, v_i, s_i, t_i$，表示第 $i$ 場鹿鹿大遊行的資訊。下一行為一個整數 $Q$。接下來 $Q$ 行，每行表示一個更改鹿鹿大遊行的行程的方式，請參考 Description 中的說明。
- $2 \le N \le 10 ^ 5$
- $1 \le M \le 3 \times 10 ^ 5$
- $1 \le Q \le 3 \times 10 ^ 5$
- $1 \le u_i, v_i \le N$
- $u_i \ne v_i$
- $1 \le s_i \le t_i \le 10 ^ 9$
- 對於每一個第 $1$ 種修改遊行的行程的方式：
- $1 \le i \le M$
- $1 \le s_i' \le t_i' \le 10 ^ 9$
- 對於每一個第 $2$ 種修改遊行的行程的方式：
- $1 \le i \le M$
- 對於每一個第 $3$ 種修改遊行的行程的方式：
- $1 \le u', v' \le N$
- $u' \ne v'$
- $1 \le s' \le t' \le 10 ^ 9$
Output Format
對於每一個更改鹿鹿大遊行的行程的方式，如果修改後無法抵達鹿園，請輸出 -1；否則，請輸出一行包含一整數，表示在開園後最快能抵達鹿園的時間。
Sample Input 1
1 2 1 3
1 2 5 7
3 1 1 9
2 3 2 4
2 3 6 8
4
2 2
3 1 3 1 2
1 2 1 2
2 5
Sample Output 1
2
4
-1
Sample Input 2
1 2 2 2
1 2 1 3
1 3 3 5
1 3 1 5
4
1 3 2 3
1 4 1 1
2 4
3 2 3 3 4
Sample Output 2
1
5
4
Sample Input 3
1 2 50 59
1 3 53 54
1 2 74 95
3 2 72 75
1 2 70 72
1 3 12 63
2 3 4 36
1 2 67 83
3 2 33 71
5 4 12 92
7 5 21 54
4 7 1 43
5 6 39 48
4 5 28 66
7 4 76 98
5 4 38 47
6 7 42 60
4 7 43 82
4
3 1 7 10 35
3 3 4 58 61
3 1 7 33 83
3 3 7 92 94
Sample Output 3
-1
83
94
Hints
第一筆範例測資中，每個更改方式及其說明分別如下：
- 第一個更改方式：取消第 $2$ 場鹿鹿大遊行。 旅客可以透過第 $1$ 場鹿鹿大遊行在時間 $3$ 抵達 $2$ 號區域，再透過第 $5$ 場鹿鹿大遊行在時間 $8$ 抵達鹿園。注意到旅客由於旅客在時間 $3$ 才抵達 $2$ 號區域，故無法趕上第 $4$ 場鹿鹿大遊行。
- 第二個更改方式：新增一場鹿鹿大遊行。在時間 $1$ 從區域 $1$ 開始，並在時間 $2$ 抵達區域 $3$。 旅客可以直接透過新增的鹿鹿大遊行，在時間 $2$ 抵達鹿園。
- 第三個更改方式：將第 $1$ 場鹿鹿大遊行改為從時間 $1$ 開始，並會在時間 $2$ 抵達目的地。 旅客可以透過更改過後的第 $1$ 場鹿鹿大遊行在時間 $2$ 抵達 $2$ 號區域，即可透過第 $4$ 場鹿鹿大遊行在時間 $4$ 抵達鹿園。
- 第四個更改方式：取消第 $5$ 場鹿鹿大遊行。
取消後旅客即無法透過鹿鹿大遊行從園區入口抵達鹿園，故輸出
-1。
Problem Source
改編自 2024 台清交程式競賽 pG - Nathan's Adventure
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0~17 | $N \le 2000, M \le 2000, Q \le 2000$ | 10 |
| 3 | 18~29 | 對於每個更改後的所有鹿鹿大遊行（包含修改時間或新增的），皆滿足開始時間 s 與抵達時間 t 相同；且更改後所有鹿鹿大遊行之中，任兩個相異的鹿鹿大遊行的開始時間皆不相同 | 30 |
| 4 | 0~38 | 無額外限制 | 60 |