2016年2月24日 星期三

[HOJ 191][SGU 507]一個大秘寶 (題目備份)

File failed to load: file:///C:/Users/Burney/Desktop/New%20folder/191_files/extensions/MathZoom.js
HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 191 - 一個大秘寶

Problem Statistics
Solved Member: 17  Submission: 164  User Tried: 19
Problem:
hh在偉大的航道上發掘哥爾D羅傑的大秘寶。

在上次盜墓的過程,hh找到了一張地圖,意外發現那是One Piece。

One Piece是存放在一個洞窟裡,一個洞窟有n個洞穴,由n-1條路徑連接這n個洞穴,其中有m個走到底的洞穴放著秘寶,對於這m個有祕寶的洞穴,我們稱呼他為OPX,已知祕寶的價值與重量成正比,每個OPX的祕寶價值也不盡相同。

可憐的hh在登島的時候,夥伴全都被大海怪抓到海底,只有hh跟藏寶圖倖存。

因為兩手只能拿兩份秘寶,所以hh希望兩份祕寶的相差重量D越少越好,如此hh才能平衡的走出洞窟。

現在出現一個讓hh很困擾的問題,由於往回走很low,所以hh想知道若現在在洞穴Vi(非OPX),使用hh神技──觸手奪寶術!一次抓走兩份秘寶,對於往之前來的方向伸出觸手時,何時要轉彎hh不知道,所以只能一路往未探險的方向伸。

因為hh可能在任意點才發現此問題,所以請對於每個非OPX都輸出一個最小D。

為了化簡一下問題,我們定1為洞窟的起點,而只有m-n+1 ~ n是OPX。
Input:
一組測試檔有多筆測試資料。

對於每筆測試資料:
第一行有兩個數字n, m(1 ≤ m < n ≤ 200000),分別代表洞穴數與OPX
第二行有n-1個數字,分別是2~n洞穴的前一個洞穴 a2~an,保證 ai < i
第三行有m個數字,分別代表n-m+1 ~ n的OPX上的祕寶重量Ki ( -1000000 ≤ Ki ≤ 1000000 )
Output:
對於每組測試資料輸出n-m個數字於一行,每個數字以空白隔開。
若hh抓不到兩份寶藏,hh會因為不平衡摔倒,請輸出231-1,代表hh哭哭了。
Sample Input:
5 4
1 1 1 1
1 4 7 9

5 4
1 1 1 1
1 4 7 10

7 4
1 2 1 2 3 3
2 10 7 15

2 1
1
100
Sample Output:
2
3
3 3 8
2147483647
Source:
SGU 507
Problem Setter
hanhan0912
Testdata:
TestTimeMemoryScore
01000ms262144kb
12000ms262144kb10
22000ms262144kb10
32000ms262144kb10
42000ms262144kb10
56000ms262144kb10
66000ms262144kb10
76000ms262144kb10
86000ms262144kb10
96000ms262144kb10
106000ms262144kb10

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原