老人星上居住著許多的老人,這些老人的年齡高到將近百萬歲都有可能,但也有可能有不幸英年早逝的老人。
某天,老人星上的某個國度軅劁國,被一名名叫鋥盦蘄、可信度很高的巫師預言,軅劁國將會在百萬年內接連受到R顆隕石的襲擊,每一顆隕石都會不偏不倚地打在其中R條負責連接軅劁國的N座城市的E條道路上面,根據時間的不同,每條道路的炸毀時間也會不同,鋥盦蘄勸告軅劁國的M個老人們必須盡速離開軅劁國,免得遭遇不幸。
但軅劁國是一個人民都很固執的國家,沒有一個合理的理由說服這個國家的老人離開,他們是不會輕易離開軅劁國的。
為了解決這個問題,鋥盦蘄分別調查了每個老人的居住習性:如果第i個老人發現了自己的城市所在地可連通到的城市(含自己這座)少於ci座,他便會心生厭惡離開這個城市!
現在你幫鋥盦蘄寫一個程式,給你軅劁國N座城市的連通關係圖,和M個老人的ci,以及R顆隕石掉落下的倒數時間tj年和炸毀的道路編號pj,請幫每個老人找出,使得這位老人可以在定居最久(必須一直符合連通城市≥ci座)的前提下,他必須要在幾年內搬出軅劁國。
輸入首行有四個正整數N,E,R,M以空格隔開。
接著E行,第1+k行有兩個正整數ak,bk以空格隔開,代表城市ak,bk之間有一條連通道路編號為k。
接下來R行各有兩個非負整數tj,pj以空格隔開。
最後一行有M個正整數ci以空格隔開。
請輸出M行,第i行的正整數xi表示第i個老人必須要在xi年內搬出軅劁國。如果這名老人根本本來就不應該住在軅劁國,請改輸出單一一個-1;如果隕石砸完後老人居住的城市還是滿足連通性,請輸出INF。
//輸入範例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
//輸出範例1 2 4 INF //輸出範例2 -1 87 INF
本題共有四個子題,每一子題可有多筆測試資料:
第一子題的測試資料 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。
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|