TopCoder

User's AC Ratio

62.5% (10/16)

Submission's AC Ratio

25.7% (28/109)

Tags

Description

米德加市以 $24$ 小時不間斷運轉的地鐵系統聞名。此地鐵系統由 $n$ 座車站(編號為 $1, 2, \dots, n$)與 $n − 1$ 條地鐵線(分別稱為 $1$ 號線至 $n − 1$ 號線)形成,且路網中任意 $2$ 站皆可互相到達。列車運行模式如下:每條地鐵線皆為獨立運轉,且除了端點的 $2$ 座車站,中途沒有任何停靠站。$i$ 號線連接車站 $u_i$ 與 $v_i$,行車時間固定為 $w_i$ 分鐘,每天自 $u_i$ 發的首班車時刻為零時 $a_i$ 分,自 $v_i$ 發的首班車時刻為零時 $b_i$ 分,班距固定為 $p_i$ 分鐘,其中 $p_i$ 為不超過 $6$ 的正整數,而 $a_i$ 與 $b_i$ 為小於 $p_i$ 的非負整數。舉例來說,若 $u_i = 1, v_i = 2, w_i = 10, a_i = 2, b_i = 0, p_i = 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$ 筆詢問可以用四個整數 $h_i, m_i, s_i, t_i$ 表示,代表他想知道在 $h_i$ 點 $m_i$ 分,從車站 $s_i$ 利用地鐵系統到達車站 $t_i$,包含等車的所需時間。假定換車(同車站內換乘另一條地鐵線)需要恰好 $1$ 分鐘,請寫一支程式幫助克勞德得到這些詢問的答案。

Input Format

$n\ q$
$u_1\ v_1\ w_1\ a_1\ b_1\ p_1$
$u_2\ v_2\ w_2\ a_2\ b_2\ p_2$
$\vdots$
$u_{n-1}\ v_{n-1}\ w_{n-1}\ a_{n-1}\ b_{n-1}\ p_{n-1}$
$h_1\ m_1\ s_1\ t_1$
$h_2\ m_2\ s_2\ t_2$
$h_3\ m_3\ s_3\ t_3$
$h_4\ m_4\ s_4\ t_4$

  • $n$:車站數量。
  • $q$:克勞德的詢問數。
  • $u_i, v_i, w_i, a_i, b_i, p_i$ 表示 $i$ 號線連接兩車站 $u_i, v_i$,行車時間 $w_i$ 分鐘,去程首班車為零時 $a_i$ 分發,回程首班車為零時 $b_i$ 分發,且班距固定為 $p_i$ 分鐘。
  • $h_i, m_i, s_i, t_i$ 為克勞德的第 $i$ 筆詢問,代表他問你 $h_i$ 點 $m_i$ 分從車站 $s_i$ 到車站 $t_i$ 的所需時間。

Output Format

$c_1$
$c_2$
$\vdots$
$c_q$

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

Sample Input

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

26
30
1
15
20

Hints

測資限制

  • $2\leq n\leq 5\times 10^ 4$。
  • $1\leq q\leq 2\times 10^ 5$。
  • $1\leq u_i,v_i\leq n$,$1\leq w_i\leq 1000$。($i\in\{1,2,\dots,n-1\}$)
  • $1\leq p_i\leq 6$,$0\leq a_i,b_i\leq p_i-1$。($i\in\{1,2,\dots,n-1\}$)
  • $0\leq h_i\leq 23$,$0\leq m_i\leq 59$。($i\in\{1,2,\dots,q\}$)
  • $1\leq s_i,t_i\leq n$,且 $s_i\neq t_i$。($i\in\{1,2,\dots,q\}$)
  • 給定的 $n-1$ 條地鐵線恰可以連通 $n$ 座車站。
  • 輸入的數皆為整數。

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

  1. (16%) $n\leq 500$。
  2. (31%) 對於所有的 $i=1,2\dots,n-1$,皆有 $p_i=1$。
  3. (37%) 對於所有的 $i=1,2,\dots,n-1$,皆有 $u_i=i, v_i=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 $n\leq 500$ 16
2 10~19 對於所有的 $i=1,2\dots,n-1$,皆有 $p_i=1$。 31
3 20~29 對於所有的 $i=1,2,\dots,n-1$,皆有 $u_i=i, v_i=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