370 . 邪教的咒語
TopCoder
Description
某天眼皮醬跟起司豬在討論某種邪教咒語的規律
「聽起來好洗腦喔~」
「怎麼都在那幾個音跳來跳去~」
「你不要再放了，你每天放我都快要可以背起來了!」
「亞八里~亞八里~向姊轉轉~」
「這段咒語的結尾可以直接接到另外那段咒語的開頭耶!」
「不要跟著節奏轉肚皮啦!」
「轉~轉~轉~」
「是說既然可以咒語之間有連結關係，那我們可以把咒語接起來咯~」
「那我們可以把咒語接成多長啊?」
這時候問題就來了
給你一堆邪教咒語，還有之間的連接關係，問你可以把咒語接的多長(咒語可以重複使用)?
為了方便計算，我們把咒語切成許多等長的音
Input Format
每個檔案開頭有一個整數$T$，代表這個檔案接下來有幾筆測資
每筆測資開頭有兩個整數$N,M$，代表有$N$條咒語，咒語之間的關係有$M$個
接下來的一行有$N$個數字$a_{1}, a_{2}, a_{3}...a_{i}...a_{N}$，代表咒語i的長度
接下來$M$行，每行四個數字$s1,t1,s2,t2$，代表咒語$s1$第$t1$個音結束的瞬間可以直接接到$s2$第$t2$個音的前面
1 ≦ $T$ ≦ 10
1 ≦ $N$ ≦ 105
0 ≦ $M$ ≦ 5*105
1 ≦ $a_{i}$ ≦ 108
1 ≦ $s1,s2$ ≦ $N$
1 ≦ $t1$ ≦ $a_{s1}$
1 ≦ $t2$ ≦ $a_{s2}$
Output Format
對每筆測資請輸出重新組合後的咒語最多會有多少個音 如果長度是無限長的話，請輸出"LoveLive!"(不含引號) 每筆測資之間要換行
Sample Input 1
2
3 3
10 10 10
1 5 2 3
2 7 1 6
2 3 3 5
1 1
10
1 6 1 3
3 3
10 10 10
1 5 2 3
2 7 1 6
2 3 3 5
1 1
10
1 6 1 3
Sample Output 1
15
LoveLive!
LoveLive!
Problem Source
NEOJ Problem 417
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 1 ≦ $N,M$ ≦ 103 且 1 ≦ $a_{i}$ ≦ 103 | 30 |
| 2 | 0~1 | 1 ≦ $N,M$ ≦ 104 且 1 ≦ $a_{i}$ ≦ 108 | 30 |
| 3 | 2~4 | 無額外限制 | 40 |