967 . 小森愛吃肉

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

littlecube

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (5/5)

Tags

ytp ytp-senior ytp-2025

Description

小森是一個天真爛漫又可愛的尼特族，她最近搬到了蔬菜王國。蔬菜王國總共有 $N$ 個城鎮，城鎮跟城鎮之間總共有 $M$ 條雙向道路連通。第 $i$ 條道路連接著 $U_i, V_i$ 兩個城鎮。但是由於蔬菜王國的道路建設技術有限，第 $i$ 條路只在第 $L_i$ 到 $R_i$ 天才會開放通行。

雖然蔬菜王國的生活很悠閒，每天直播就可以獲得不少的收入，但是小森搬來之後才發現，在這裡居然幾乎沒有她最愛的肉可以吃！這對小森來說宛如晴天霹靂。不過，在一番搜尋後，她成功找到了 $Q$ 家餐廳有供應肉類料理。第 $j$ 家餐廳在第 $A_j$ 號城鎮。並且只在第 $S_j$ 到 $T_j$ 天無限量供應肉類，每吃一次第 $j$ 家餐廳的食物可以讓小森獲得 $C_j$ 單位的滿足度。

獲得這些資訊後，小森決定要規劃一趟朝聖肉食之旅。這趟旅行總共持續 $10^ 9$ 天。在每一天的白天時，她可以任意沿著當天有開放的道路自由移動，走訪的城鎮數量沒有限制，在每個造訪的城鎮裡，她可以光顧當天有營業的所有餐廳。她當天獲得的滿足度是她光顧的所有餐廳能帶給他的滿足度的總和。但她不喜歡吃重複的食物，因此同一間餐廳每天最多只能吃一次。另外她也不想要露宿街頭，因此在每一天的晚上時她必須剛好停留在某個城鎮裡面過夜，並從這個城鎮展開隔天的行程。

現在她想要問，對於所有的可能的起點城鎮，她能獲得的滿足度的總和最多是多少。

Input Format

第一行是三個正整數 $N, M, Q$。

接下來的 $M$ 行，每行有四個正整數，第 $i$ 行分別是 $U_i, V_i, L_i, R_i$，代表第 $i$ 條道路連接著 $U_i, V_i$ 兩個城鎮，並且只在第 $L_i$ 到 $R_i$ 天開放。

接下來的 $Q$ 行，每行有四個正整數，第 $j$ 行分別是 $A_j, C_j, S_j, T_j$，代表第 $j$ 家餐廳在第 $A_j$ 號城鎮，每吃一次可以給小森 $C_j$ 的滿足度，並且只在第 $S_j$ 到第 $T_j$ 天供應肉類。

  • $1 \leq N \leq 10^ 5$
  • $0 \leq M \leq 10^ 5$
  • $0 \leq Q \leq 10^ 5$
  • $1 \leq U_i, V_i \leq N$
  • $U_i \neq V_i$
  • $1 \leq L_i \leq R_i \leq 10^ 9$
  • $1 \leq A_j \leq N$
  • $1 \leq C_j \leq 10^ 4$
  • $1 \leq S_j \leq T_j \leq 10^ 9$

Output Format

輸出 $N$ 個非負整數，第 $i$ 個非負整數代表以第 $i$ 個城鎮作為起點的最大滿足度總和。

Sample Input 1

3 3 3
1 2 2 2
2 3 2 3
1 3 4 4
2 6 1 3
3 3 2 4
1 2 3 3

Sample Output 1

21
27
21

Sample Input 2

5 8 4
1 2 7 9
1 3 4 4
2 5 8 9
5 2 1 2
3 4 3 6
4 5 6 9
2 4 1 1
1 3 8 8
2 4 1 2
3 3 3 7
2 10 7 8
1 9 5 6

Sample Output 2

41
48
44
48
48

Hints

在範例測試資料一中，如果小森從 $1$ 號城鎮出發，那麼她的一個可以獲得最大滿足度的路線如下：

  • 第一天的白天不去任何餐廳，獲得 $0$ 的滿足度。第一天的晚上在 $1$ 號城鎮過夜。
  • 第二天的白天去第一跟第二家餐廳，獲得 $9$ 的滿足度。第二天的晚上在 $2$ 號城鎮過夜。
  • 第三天的白天去第一跟第二家餐廳，獲得 $9$ 的滿足度。第三天的晚上在 $3$ 號城鎮過夜。
  • 第四天的白天去第二家餐廳，獲得 $3$ 的滿足度。第四天的晚上在 $3$ 號城鎮過夜。

從第五天開始，因為沒有任何一家餐廳還有供應肉類，因此小森總共獲得 $9 + 9 + 3 = 21$ 單位的滿足度。

如果小森在第二天的晚上在 $1$ 號城鎮過夜，則他可以在第三天去第三家餐廳，但是無法在第三天去第一或第二家餐廳，因此總共只能獲得 $14$ 單位的滿足度。

Problem Source

YTP 2025 高中組程式挑戰營 p17

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測試資料 0
2 0~18 $R_i \leq 15, T_j \leq 15$ 5
3 0~1, 19~32 $N, M, Q \leq 2000$ 4
4 0~18, 33~43 $R_i \leq 10^ 5, T_j \leq 10^ 5$ 8
5 0~55 無額外限制 8

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 2097152 65536 1 2 3 4 5
1 4000 2097152 65536 1 2 3 4 5
2 4000 2097152 65536 2 4 5
3 4000 2097152 65536 2 4 5
4 4000 2097152 65536 2 4 5
5 4000 2097152 65536 2 4 5
6 4000 2097152 65536 2 4 5
7 4000 2097152 65536 2 4 5
8 4000 2097152 65536 2 4 5
9 4000 2097152 65536 2 4 5
10 4000 2097152 65536 2 4 5
11 4000 2097152 65536 2 4 5
12 4000 2097152 65536 2 4 5
13 4000 2097152 65536 2 4 5
14 4000 2097152 65536 2 4 5
15 4000 2097152 65536 2 4 5
16 4000 2097152 65536 2 4 5
17 4000 2097152 65536 2 4 5
18 4000 2097152 65536 2 4 5
19 4000 2097152 65536 3 5
20 4000 2097152 65536 3 5
21 4000 2097152 65536 3 5
22 4000 2097152 65536 3 5
23 4000 2097152 65536 3 5
24 4000 2097152 65536 3 5
25 4000 2097152 65536 3 5
26 4000 2097152 65536 3 5
27 4000 2097152 65536 3 5
28 4000 2097152 65536 3 5
29 4000 2097152 65536 3 5
30 4000 2097152 65536 3 5
31 4000 2097152 65536 3 5
32 4000 2097152 65536 3 5
33 4000 2097152 65536 4 5
34 4000 2097152 65536 4 5
35 4000 2097152 65536 4 5
36 4000 2097152 65536 4 5
37 4000 2097152 65536 4 5
38 4000 2097152 65536 4 5
39 4000 2097152 65536 4 5
40 4000 2097152 65536 4 5
41 4000 2097152 65536 4 5
42 4000 2097152 65536 4 5
43 4000 2097152 65536 4 5
44 4000 2097152 65536 5
45 4000 2097152 65536 5
46 4000 2097152 65536 5
47 4000 2097152 65536 5
48 4000 2097152 65536 5
49 4000 2097152 65536 5
50 4000 2097152 65536 5
51 4000 2097152 65536 5
52 4000 2097152 65536 5
53 4000 2097152 65536 5
54 4000 2097152 65536 5
55 4000 2097152 65536 5
Submit
Back to Top