5 . 高速公鹿

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

hank55663

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

44.4% (4/9)

Tags

ntucpc-challenge1

Description


日野動物園特有的鹿鹿大遊行

由於日野動物園腹地廣大，園方正考慮將「鹿鹿大遊行」作為一種交通方式，讓旅客搭乘鹿在園區內不同的區域之間移動。

日野動物園內一共有 N 個不同的區域，區域以 1 到 N 的整數編號，其中第 1 個區域為園區入口，而第 N 個區域是最熱門的區域——鹿園。日野動物園每天一共有 M 場鹿鹿大遊行，園方將每天的營業時間分成 109 等分，開園時為時間 1，閉園時為時間 109。第 i 場的鹿鹿大遊行將在時間 si 從區域 ui 開始，並在時間 ti 抵達區域 vi。

由於大部分的旅客在進入園區後都直接前往鹿園，因此日野動物園評估路線的方式為：開園時從園區入口開始，搭乘鹿鹿大遊行最快能在哪個時間點抵達鹿園。旅客只能透過鹿鹿大遊行移動，在沒有搭乘鹿鹿大遊行時必須停在原本所在的區域。如果要搭乘鹿鹿大遊行，旅客必須在鹿鹿大遊行開始的時間點或開始之前抵達該區域。

最近園方打算更動鹿鹿大遊行的行程，他們列出了 Q 個更改的方式。每一個方式可能是以下的其中一種：

  • 1 i si′ ti′：表示第 i 場的鹿鹿大遊行被改為從時間 si′ 開始，並會在時間 ti′ 抵達目的地。
  • 2 i：取消第 i 場的鹿鹿大遊行。
  • 3 u′ v′ s′ t′：新增一場鹿鹿大遊行在時間 s′ 從區域 u′ 開始，並在時間 t′ 抵達區域 v′。

日野動物園想知道，鹿鹿大遊行的行程在分別經過這些修改的方式後，開園時透過鹿鹿大遊行從園區入口到鹿園需要花多少時間。注意 Q 個更改的方式之間是沒有關聯的，也就是說，園方想知道的是，對於每一個更改的方式，用原本的行程進行該更改後，最快能抵達鹿園的時間。你能寫一支程式幫助日野動物園嗎？

Input Format

輸入的第一行包含兩個整數 N,M。接下來 M 行，每行包含四個整數 ui,vi,si,ti，表示第 i 場鹿鹿大遊行的資訊。下一行為一個整數 Q。接下來 Q 行，每行表示一個更改鹿鹿大遊行的行程的方式，請參考 Description 中的說明。

  • 2≤N≤105
  • 1≤M≤3×105
  • 1≤Q≤3×105
  • 1≤ui,vi≤N
  • ui≠vi
  • 1≤si≤ti≤109
  • 對於每一個第 1 種修改遊行的行程的方式：
    • 1≤i≤M
    • 1≤si′≤ti′≤109
  • 對於每一個第 2 種修改遊行的行程的方式：
    • 1≤i≤M
  • 對於每一個第 3 種修改遊行的行程的方式：
    • 1≤u′,v′≤N
    • u′≠v′
    • 1≤s′≤t′≤109

Output Format

對於每一個更改鹿鹿大遊行的行程的方式，如果修改後無法抵達鹿園，請輸出 -1；否則，請輸出一行包含一整數，表示在開園後最快能抵達鹿園的時間。

Sample Input 1

3 5
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

8
2
4
-1

Sample Input 2

3 4
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

3
1
5
4

Sample Input 3

7 18
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

35
-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≤2000,M≤2000,Q≤2000 10
3 18~29 對於每個更改後的所有鹿鹿大遊行（包含修改時間或新增的），皆滿足開始時間 s 與抵達時間 t 相同；且更改後所有鹿鹿大遊行之中，任兩個相異的鹿鹿大遊行的開始時間皆不相同 30
4 0~38 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 2097152 65536 1 2 4
1 3000 2097152 65536 1 2 4
2 3000 2097152 65536 1 2 4
3 3000 2097152 65536 2 4
4 3000 2097152 65536 2 4
5 3000 2097152 65536 2 4
6 3000 2097152 65536 2 4
7 3000 2097152 65536 2 4
8 3000 2097152 65536 2 4
9 3000 2097152 65536 2 4
10 3000 2097152 65536 2 4
11 3000 2097152 65536 2 4
12 3000 2097152 65536 2 4
13 3000 2097152 65536 2 4
14 3000 2097152 65536 2 4
15 3000 2097152 65536 2 4
16 3000 2097152 65536 2 4
17 3000 2097152 65536 2 4
18 3000 2097152 65536 3 4
19 3000 2097152 65536 3 4
20 3000 2097152 65536 3 4
21 3000 2097152 65536 3 4
22 3000 2097152 65536 3 4
23 3000 2097152 65536 3 4
24 3000 2097152 65536 3 4
25 3000 2097152 65536 3 4
26 3000 2097152 65536 3 4
27 3000 2097152 65536 3 4
28 3000 2097152 65536 3 4
29 3000 2097152 65536 3 4
30 3000 2097152 65536 4
31 3000 2097152 65536 4
32 3000 2097152 65536 4
33 3000 2097152 65536 4
34 3000 2097152 65536 4
35 3000 2097152 65536 4
36 3000 2097152 65536 4
37 3000 2097152 65536 4
38 3000 2097152 65536 4
Submit
Back to Top