104 . 迷宮設置

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

77.8% (7/9)

Submission's AC Ratio

20.6% (7/34)

Tags

ioicamp ioicamp-2023

Description

朱拉．坦派斯特聯邦國的迷宮最近被天使大軍弄得一團亂，利姆路決定要來增強迷宮的強度。迷宮一共由 N 個空間組成，其中第一個空間是入口，其他的空間則必須透過設置在另一個空間內的傳送門才能進入。

利姆路每次會挑選一個擁有特定戰力及魔力的惡魔派到某個空間。當一個惡魔進入了某個空間後，如果它的魔力用完了，它就會停在那間空間內；如果它還有魔力，它就會消耗一點魔力後分身成無數個擁有相同魔力與戰力的「並列存在」，並且從空間中消失，之後每個並列存在會沿著那間空間內的某個傳送門前往另一個空間，不過每次一道傳送門只能有一個並列存在通過，而多出來的並列存在會直接消失。擁有魔力的並列存在進到新的空間後也會繼續進行分身。

為了好好配置迷宮的戰力，在一個惡魔的每個並列存在都停下或消失後，那些停下的並列存在會回報它們所在的空間的總戰力，讓利姆路決定下次要如何派遣惡魔。總戰力包含那些空間內的初始戰力以及每個停在那些空間內的並列存在的戰力總和。

Input Format

輸入第一行包含兩個正整數 N,Q，分別代表空間數量及派遣次數。

第二行包含 N 個整數 s1,s2,…,sN，其中 si 代表第 i 個空間的初始戰力。

第三行包含 N−1 個整數 d2,d3,…,dN，其中 di 代表通往第 i 個空間的傳送門位於哪個空間內。

接下來有 Q 行，第 i 行包含六個整數 ui,vi,wi,xi,yi,zi，代表第 i 次派遣惡魔的策略，假設前一次惡魔回報的總戰力為 lasti−1，則這次派出的惡魔擁有 (ui×lasti−1+vi)mod106 的戰力、(wi×lasti−1+xi)modN 的魔力，並且會派到第 ((yi×lasti−1+zi)modN)+1 個空間。第一次派遣時，last0 為 0。

  • 2≤N,Q≤5×105
  • 0≤si≤106
  • 1≤di≤N
  • 0≤ui,vi,wi,xi,yi,zi≤106
  • 從入口出發能經過一些傳送門到達任何一間空間
  • 保證每次至少有一個並列存在不會消失

Output Format

在每一次派遣後，輸出一行包含一個整數代表這次的並列存在停留位置的總戰力。

Sample Input 1

6 3
0 0 0 3 2 1
6 6 1 3 4
0 6 5 0 8 4
7 4 6 1 0 2
1 0 6 2 1 1

Sample Output 1

8
68
136

Sample Input 2

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

Sample Output 2

11
56
299
603
3688
7678

Hints

Problem Source

IOICamp 2023 Day2 pD

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~30 ui,wi,yi=0 40
3 0~59 無其他限制 60

Testdata and Limits

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