c497. 二、老人與隕石(Meteorite)
Tags :
Accepted rate : 7人/7人 ( 100% ) [非即時]
評分方式:
Strictly

最近更新 : 2018-01-28 16:18

Content

  老人星上居住著許多的老人,這些老人的年齡高到將近百萬歲都有可能,但也有可能有不幸英年早逝的老人。

  某天,老人星上的某個國度軅劁國,被一名名叫鋥盦蘄、可信度很高的巫師預言,軅劁國將會在百萬年內接連受到R顆隕石的襲擊,每一顆隕石都會不偏不倚地打在其中R條負責連接軅劁國的N座城市的E條道路上面,根據時間的不同,每條道路的炸毀時間也會不同,鋥盦蘄勸告軅劁國的M個老人們必須盡速離開軅劁國,免得遭遇不幸。

  但軅劁國是一個人民都很固執的國家,沒有一個合理的理由說服這個國家的老人離開,他們是不會輕易離開軅劁國的。

  為了解決這個問題,鋥盦蘄分別調查了每個老人的居住習性:如果第i個老人發現了自己的城市所在地可連通到的城市(含自己這座)少於ci座,他便會心生厭惡離開這個城市!

  現在你幫鋥盦蘄寫一個程式,給你軅劁國N座城市的連通關係圖,和M個老人的ci,以及R顆隕石掉落下的倒數時間tj年和炸毀的道路編號pj,請幫每個老人找出,使得這位老人可以在定居最久(必須一直符合連通城市≥ci座)的前提下,他必須要在幾年內搬出軅劁國。

Input

輸入首行有四個正整數N,E,R,M以空格隔開。
接著E行,第1+k行有兩個正整數ak,bk以空格隔開,代表城市ak,bk之間有一條連通道路編號為k。
接下來R行各有兩個非負整數tj,pj以空格隔開。
最後一行有M個正整數ci以空格隔開。

Output

請輸出M行,第i行的正整數xi表示第i個老人必須要在xi年內搬出軅劁國。如果這名老人根本本來就不應該住在軅劁國,請改輸出單一一個-1;如果隕石砸完後老人居住的城市還是滿足連通性,請輸出INF。

Sample Input #1
//輸入範例1
5 6 4 3
1 2
5 1
4 5
2 3
1 3
3 4
1 2
2 6
3 1
4 4
5 3 1

//輸入範例2
5 4 3 3
1 2
3 4
4 5
3 5
6 1
9 2
87 3
5 3 2
Sample Output #1
//輸出範例1
2
4
INF

//輸出範例2
-1
87
INF
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (16%): 1.0s , <1M
不公開 測資點#1 (1%): 1.0s , <1M
不公開 測資點#2 (1%): 1.0s , <1M
不公開 測資點#3 (33%): 1.0s , <50M
不公開 測資點#4 (1%): 1.0s , <50M
不公開 測資點#5 (1%): 1.0s , <50M
不公開 測資點#6 (35%): 1.0s , <50M
不公開 測資點#7 (1%): 1.0s , <50M
不公開 測資點#8 (1%): 1.0s , <10M
不公開 測資點#9 (8%): 0.5s , <50M
不公開 測資點#10 (1%): 0.5s , <10M
不公開 測資點#11 (1%): 0.5s , <50M
Hint :

本題共有四個子題,每一子題可有多筆測試資料:
第一子題的測試資料 N≤500,M≤103,E≤5×103,全部解出可獲18分;
第二子題的測試資料 N≤105,M=1,E≤5×105,全部解出可獲35分;
第三子題的測試資料 N≤105,M≤105,E≤5×105,全部解出可獲37分;
第四子題的測試資料 N≤105,M≤106,E≤5×105,時限下修至0.5s,全部解出可獲10分。
所有測試資料,1≤a,b,ci≤N,tj≤106,0≤R≤E,1≤pj≤E,ak≠bk
如果x≠y,則px≠py

 

Tags:
出處:
板橋高中模擬賽 [管理者: baluteshih (波路特石) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」