TopCoder

User's AC Ratio

52.9% (18/34)

Submission's AC Ratio

19.9% (54/272)

Tags

Description

米德加市以 24 小時不間斷運轉的地鐵系統聞名。此地鐵系統由 n 座車站(編號為 1,2,,n)與 n1 條地鐵線(分別稱為 1 號線至 n1 號線)形成,且路網中任意 2 站皆可互相到達。列車運行模式如下:每條地鐵線皆為獨立運轉,且除了端點的 2 座車站,中途沒有任何停靠站。i 號線連接車站 uivi,行車時間固定為 wi 分鐘,每天自 ui 發的首班車時刻為零時 ai 分,自 vi 發的首班車時刻為零時 bi 分,班距固定為 pi 分鐘,其中 pi 為不超過 6 的正整數,而 aibi 為小於 pi 的非負整數。舉例來說,若 ui=1,vi=2,wi=10,ai=2,bi=0,pi=5,則每天 0:02、0:07、0:12、…、23:57 各有一班車從車站 1 開往車站 2 ,到站時刻分別為 0:12、0:17、0:22、…、0:07;回程的發車時刻則為 0:00、0:05、0:10、…、23:55,回到車站 1 的時刻分別為 0:10、0:15、0:20、…、0:05。

交通專家克勞德最近正在研究米德加市的地鐵系統,想知道在某些時間點從某些車站搭車到達另一些車站的所需時間。更精確地說,克勞德有 q 筆詢問,其中第 i 筆詢問可以用四個整數 hi,mi,si,ti 表示,代表他想知道在 himi 分,從車站 si 利用地鐵系統到達車站 ti,包含等車的所需時間。假定換車(同車站內換乘另一條地鐵線)需要恰好 1 分鐘,請寫一支程式幫助克勞德得到這些詢問的答案。

Input Format

n q
u1 v1 w1 a1 b1 p1
u2 v2 w2 a2 b2 p2

un1 vn1 wn1 an1 bn1 pn1
h1 m1 s1 t1
h2 m2 s2 t2
h3 m3 s3 t3
h4 m4 s4 t4

  • n:車站數量。
  • q:克勞德的詢問數。
  • ui,vi,wi,ai,bi,pi 表示 i 號線連接兩車站 ui,vi,行車時間 wi 分鐘,去程首班車為零時 ai 分發,回程首班車為零時 bi 分發,且班距固定為 pi 分鐘。
  • hi,mi,si,ti 為克勞德的第 i 筆詢問,代表他問你 himi 分從車站 si 到車站 ti 的所需時間。

Output Format

c1
c2

cq

  • ci 為一整數,代表第 i 筆詢問的答案,單位為分鐘。

Sample Input 1

5 5
1 2 10 2 0 5
2 3 1 0 0 1
2 4 5 2 1 3
4 5 5 0 2 4
23 35 1 5
23 35 5 1
0 1 2 3
17 30 3 5
7 20 4 1

Sample Output 1

26
30
1
15
20

Hints

測資限制

  • 2n5×104
  • 1q2×105
  • 1ui,vin1wi1000。(i{1,2,,n1}
  • 1pi60ai,bipi1。(i{1,2,,n1}
  • 0hi230mi59。(i{1,2,,q}
  • 1si,tin,且 siti。(i{1,2,,q}
  • 給定的 n1 條地鐵線恰可以連通 n 座車站。
  • 輸入的數皆為整數。

評分說明
本題共有四組子任務,條件限制如下所示。每一子任務可有一或多筆測試資料,該組所有測試資料
皆需答對才會獲得該組分數。

  1. (16%) n500
  2. (31%) 對於所有的 i=1,2,n1,皆有 pi=1
  3. (37%) 對於所有的 i=1,2,,n1,皆有 ui=i,vi=i+1
  4. (16%) 無額外限制。

範例解釋
第一筆詢問中,在 23:35 分從車站 1 出發至車站 5 的乘車過程如下:

  1. 首先搭乘 23:37 分往車站 2 的列車,於 23:47 抵達。
  2. 接著換乘 23:50 分往車站 4 的列車,於 23:55 抵達(注意需要花一分鐘轉車所以無法搭乘 23:47 發的車)。
  3. 最後換乘 23:56 分往車站 5 的列車,於隔天 0:01 抵達目的地。 包含等車與換車的所需時間為 26 分。

第三筆詢問中,搭上 0:01 的列車,於 0:02 抵達目的地,需時 1 分鐘。注意出發時不需要 1 分鐘的轉乘時間即可直接乘車。

Problem Source

2021 TOI 入營考pD
testdata set by Omelet

Subtasks

No. Testdata Range Constraints Score
1 0~9 n500 16
2 10~19 對於所有的 i=1,2,n1,皆有 pi=1 31
3 20~29 對於所有的 i=1,2,,n1,皆有 ui=i,vi=i+1 37
4 0~44 無額外限制。 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 4
1 1000 524288 65536 1 4
2 1000 524288 65536 1 4
3 1000 524288 65536 1 4
4 1000 524288 65536 1 4
5 1000 524288 65536 1 4
6 1000 524288 65536 1 4
7 1000 524288 65536 1 4
8 1000 524288 65536 1 4
9 1000 524288 65536 1 4
10 2000 524288 65536 2 4
11 2000 524288 65536 2 4
12 2000 524288 65536 2 4
13 2000 524288 65536 2 4
14 2000 524288 65536 2 4
15 2000 524288 65536 2 4
16 2000 524288 65536 2 4
17 2000 524288 65536 2 4
18 2000 524288 65536 2 4
19 2000 524288 65536 2 4
20 2000 524288 65536 3 4
21 2000 524288 65536 3 4
22 2000 524288 65536 3 4
23 2000 524288 65536 3 4
24 2000 524288 65536 3 4
25 2000 524288 65536 3 4
26 2000 524288 65536 3 4
27 2000 524288 65536 3 4
28 2000 524288 65536 3 4
29 2000 524288 65536 3 4
30 2000 524288 65536 4
31 2000 524288 65536 4
32 2000 524288 65536 4
33 2000 524288 65536 4
34 2000 524288 65536 4
35 2000 524288 65536 4
36 2000 524288 65536 4
37 2000 524288 65536 4
38 2000 524288 65536 4
39 2000 524288 65536 4
40 2000 524288 65536 4
41 2000 524288 65536 4
42 2000 524288 65536 4
43 2000 524288 65536 4
44 2000 524288 65536 4