137 . Lycoris 情報系統

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

ioicamp ioicamp-2023

Description

DA 的情報系統由 $N$ 位的 Lycoris 與楠木所組成，每位 Lycoris 都恰有一位上司，而楠木則是情報系統的最高司令。

目前每位 Lycoris 與他的上司之間都有一個通訊成本為 $d_i$ 的秘密通訊方式，且保證情報系統中的任兩位成員都可經過一連串不重複的人員來溝通，而溝通的成本則是該聯絡路徑上的成本總和，但是楠木覺得這樣的通訊方式的成本實在太高了，於是她打算基於舊有的組織架構著手打造另一套通訊方式。

具體來說，他希望在新的情報系統中建立起 $M$ 群通訊關係，其中第 $i$ 群的通訊關係會讓所有與編號 $u_i$ 的成員溝通成本不高於 $d_{1,i}$ 的成員們都與那些與編號 $v_i$ 的成員溝通成本不高於 $d_{2,i}$ 的成員們建立起一個通訊成本 $w_i$ 的新聯絡方式。

現在楠木好奇在新的情報系統中錦木千束與所有其他成員所需的溝通成本為何。

你，胡桃，做為世界最強駭客，可以幫助她嗎？

Input Format

第一行由兩個整數 $N, M$ 所組成。

第二行由 $N$ 個數字所組成，第 $i$ 個數字 $p_i$ 代表第 $i$ 號成員的上司為第 $p_i$ 號成員，其中第 $0$ 號代表楠木、第 $1$ 號代表錦木千束。

第三行由 $N$ 個數字所組成，第 $i$ 個數字 $d_i$ 代表第 $i$ 號成員與其上司的通訊成本為 $d_i$。

接下來的 $M$ 行，每行由 $5$ 個數字 $u_i, d_{1,i}, v_i, d_{2,i}, w_i$ 所組成。

  • $1 \leq N, M \leq 10^ 5$
  • $0 \leq u_i, v_i, p_i \leq N$
  • $1 \leq d_i, d_{1,i}, d_{2,i}, w_i \leq 10^ 9$
  • 輸入的秘密通訊方式保證形成樹狀結構

Output Format

輸出 $N+1$ 行整數，第 $i$ 行代表錦木千束與第 $i$ 號成員的溝通成本，若錦木千束與第 $i$ 位成員無法溝通，則請在該行輸出 -1。

Sample Input 1

5 3
0 0 0 0 0
1 2 3 4 5
0 5 1 1 10
0 2 3 4 2
5 3 2 4 6

Sample Output 1

2
0
2
2
10
6

Sample Input 2

5 5
2 0 2 3 4
7 1 2 2 100
0 10 3 2 7
1 2 4 10 1
2 1 5 1 2
0 2 5 6 2
1 8 4 99 100

Sample Output 2

1
0
1
1
1
3

Hints

Problem Source

IOICamp 2023 Day5 pL

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~36 $\forall 1\leq i \leq N, p_i = i-1$ 30
3 0~106 無特別限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 1048576 65536 1 3
1 4000 1048576 65536 1 3
2 4000 1048576 65536 2 3
3 4000 1048576 65536 2 3
4 4000 1048576 65536 2 3
5 4000 1048576 65536 2 3
6 4000 1048576 65536 2 3
7 4000 1048576 65536 2 3
8 4000 1048576 65536 2 3
9 4000 1048576 65536 2 3
10 4000 1048576 65536 2 3
11 4000 1048576 65536 2 3
12 4000 1048576 65536 2 3
13 4000 1048576 65536 2 3
14 4000 1048576 65536 2 3
15 4000 1048576 65536 2 3
16 4000 1048576 65536 2 3
17 4000 1048576 65536 2 3
18 4000 1048576 65536 2 3
19 4000 1048576 65536 2 3
20 4000 1048576 65536 2 3
21 4000 1048576 65536 2 3
22 4000 1048576 65536 2 3
23 4000 1048576 65536 2 3
24 4000 1048576 65536 2 3
25 4000 1048576 65536 2 3
26 4000 1048576 65536 2 3
27 4000 1048576 65536 2 3
28 4000 1048576 65536 2 3
29 4000 1048576 65536 2 3
30 4000 1048576 65536 2 3
31 4000 1048576 65536 2 3
32 4000 1048576 65536 2 3
33 4000 1048576 65536 2 3
34 4000 1048576 65536 2 3
35 4000 1048576 65536 2 3
36 4000 1048576 65536 2 3
37 4000 1048576 65536 3
38 4000 1048576 65536 3
39 4000 1048576 65536 3
40 4000 1048576 65536 3
41 4000 1048576 65536 3
42 4000 1048576 65536 3
43 4000 1048576 65536 3
44 4000 1048576 65536 3
45 4000 1048576 65536 3
46 4000 1048576 65536 3
47 4000 1048576 65536 3
48 4000 1048576 65536 3
49 4000 1048576 65536 3
50 4000 1048576 65536 3
51 4000 1048576 65536 3
52 4000 1048576 65536 3
53 4000 1048576 65536 3
54 4000 1048576 65536 3
55 4000 1048576 65536 3
56 4000 1048576 65536 3
57 4000 1048576 65536 3
58 4000 1048576 65536 3
59 4000 1048576 65536 3
60 4000 1048576 65536 3
61 4000 1048576 65536 3
62 4000 1048576 65536 3
63 4000 1048576 65536 3
64 4000 1048576 65536 3
65 4000 1048576 65536 3
66 4000 1048576 65536 3
67 4000 1048576 65536 3
68 4000 1048576 65536 3
69 4000 1048576 65536 3
70 4000 1048576 65536 3
71 4000 1048576 65536 3
72 4000 1048576 65536 3
73 4000 1048576 65536 3
74 4000 1048576 65536 3
75 4000 1048576 65536 3
76 4000 1048576 65536 3
77 4000 1048576 65536 3
78 4000 1048576 65536 3
79 4000 1048576 65536 3
80 4000 1048576 65536 3
81 4000 1048576 65536 3
82 4000 1048576 65536 3
83 4000 1048576 65536 3
84 4000 1048576 65536 3
85 4000 1048576 65536 3
86 4000 1048576 65536 3
87 4000 1048576 65536 3
88 4000 1048576 65536 3
89 4000 1048576 65536 3
90 4000 1048576 65536 3
91 4000 1048576 65536 3
92 4000 1048576 65536 3
93 4000 1048576 65536 3
94 4000 1048576 65536 3
95 4000 1048576 65536 3
96 4000 1048576 65536 3
97 4000 1048576 65536 3
98 4000 1048576 65536 3
99 4000 1048576 65536 3
100 4000 1048576 65536 3
101 4000 1048576 65536 3
102 4000 1048576 65536 3
103 4000 1048576 65536 3
104 4000 1048576 65536 3
105 4000 1048576 65536 3
106 4000 1048576 65536 3
Submit
Back to Top