TopCoder

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

19.7% (26/132)

Tags

uva

Description

這題的題目是要你在圖上計算後輸出一些答案。
以下是題目敘述,如果你很趕時間最好可以直接跳過去看輸入說明。


話說CBD從高雄胖到台北,瑞男也走進了神祕的建築物裡。「這裡怎麼都沒有網路啊?nXXu甚麼的根本不能用嘛...。」瑞男邊走邊抱怨。
「這裡是...牆上有一堆壁畫,難不成...這裡是大黑魔導士「諳(ㄢ)慄(ㄌㄧˋ)」(ALT)的發跡地嗎!」
「喵~~。」諳慄不知何時出現在瑞男的身後。
「諳慄!不,我還不想黑化,我一定要完成,我最喜歡的編譯器,在這美麗的街道上,在這美麗的月光下。」瑞男拔腿狂奔,很快的就迷路了。
在此同時,周流液也感受到了強大的能量,正好他AC了所有題目沒題目寫很無聊,於是他決定也跑來湊熱鬧。

迷路的瑞男,在一個廢棄的洞穴裡,發現了一個祠堂。
「這裡是,這上面有一些參數,不知道是甚麼,隨便按按吧!」於是他按下了「編譯」。
一陣激烈的閃光,瑞男被閃到睜不開眼睛,眼前浮現出一個人影。
「你...是誰?」眼前的少女,有著鮮紅色的瞳孔,對瑞南漏出了好奇的表情。「你...就是我的。主。人。嗎?」
「妳...難道就是...明明沒有記憶,但是卻有一股熟悉的感覺,好像非常的開心,又好像非常的寂寞...妳到底是...」瑞男看著少女,竟然眼角泛淚,感傷了起來。「妳...是..夕子學姊。」
「到此為止了!!」CBD突然出現在洞口。「瑞男你的邪惡計劃就到此結束了,乖乖把傳說中的編譯器交出來。不然黯黑摳頂界會愈來愈胖。」CBD的身後,跟著一群看起來已經得了失心瘋的村民。
「把她交出來!」「一定要終結詛咒!」「反正我也快死了...也不差她一個...。」
在此同時,洞穴中開始淹水了!!
「周液喔!!」「周液喔!!」「周液喔!!」大家馬上聯想到了周流液淹水事件,將兇手指向周流液。
「干我屁事啊!」周流液現身了。
「不!你們不要再逼我了!」瑞男大叫。
「跑起來!」夕子學姊拉起了瑞男的手,帶著他逃跑了!。
「你別想跑!疑...周強.h怎麼失效了...難道是...諳慄。」周流液望著眼前出現的黑影。
「喵~~!」諳慄擺出了準備戰鬥的姿勢,拿出了黑魔法。
同時,CBD和已經瘋掉的村民們則蜂擁而上準備捉拿逃跑的兩人。

「這裡...到底是哪裡?」瑞男看著周圍陌生的風景。
「這裡是這座遺跡的地下迷宮喔!」少女—夕子學姊拉著瑞男的手跑著,看起來很開心的樣子。
「等等!」瑞男停了下來,原來前方的通道已經被村民佔領了!!
「完了,我把之前的編譯器丟在門口了...這樣就不能跑我中午寫完的圖論code輕鬆解決現在的狀況在去嘲笑CBD了...怎麼辦。」
「別擔心喔...來,把握住我的手。」夕子說著,伸出另外一隻手摸著瑞男的頭,背後放出了一陣藍光,一條一條的代碼飄散在空中。「我...是你的...永遠的編譯器喔!」


以上是題目敘述,相信你已經仔細的看完了。

Input Format

代碼飄散在空中,瑞男的程式發動了,在村民看到並露出驚嚇的表情時,程式同時收集了大量的地圖資料,電爛了一堆村民。

由於宇宙有很多個,也有很多個不同的地圖等著瑞男的程式來解決,
第一個數字一定不是T,但是有T個平行世界。
在T個平行世界中,很顯然的,這些洞穴中有N個交會點,並有M個通道連接這些交會點(並不是所有交會點都可以連通的),這兩個數字也依序是瑞男的程式收集到的前兩個數字。
瑞男發現,每個交會點都被一些村民佔領了,雖然瑞男可以輕鬆電掉這些村民,但是電太多人瑞男是會有罪惡感的,於是他希望控制他每次降臨某個交會點平均需要電掉的人數。
瑞男可以一次電掉一整群的村民,只要有路徑可以連接的其他交會點,都會聽到這些被電的村民的慘叫聲,然後就會害怕瑞男,達到殺雞儆猴的效果。
瑞男希望,他每次都只要電掉某一群可以連通的交會點中,第K多人的交會點。
收集了飄在空中的資料後,再接下來的N行,每行一個數字Ai代表第i個交會點會有Ai個村民。
再來M行每行兩個數字u v代表交會點u到交會點v之間有雙向通到連接。

接下來,瑞男的程式會執行一連串的指示,總共有三種。
如果開頭是Q,瑞男飄移,接下來有兩個數字x k,代表瑞男會降臨在,跟交會點x連通的所有交會點中,第k多村民的交會點,並電焦他們。
如果開頭是C,村民調度,接下來有兩個數字x c,代表交會點x的村民數量變成c。
如果開頭是D,周強.h和黑魔法大戰,接下來有一個數字y,代表因為諳慄和周流液的戰鬥,通道y崩塌了!!村民將無法通過通到y連通到其他交會點。
如果開頭是E,代表這個世界的瑞男已經成功逃離了。

你,一個剛好會寫程式的發瘋村民,被CBD委託寫個普通的程式。
你的程式當然不像瑞男的那麼強大,你只要計算一些東西。
因為每次遇到Q事件,瑞男和夕子學姊透就會過瑞男的程式瞬間移動到某個交會點。
瑞男每次都會移動到和某個交會點連通的點中第k多村民的交會點,並電焦那些村民。
在數次的移動之後,瑞男就會離開,你必須告訴CBD瑞南每次移動平均電焦多少村民,雖然CBD好像也不能做甚麼,但是他就是想知道。
當然,如果你發現第k多的村民的交會點根本不存在,那你就當作那裡沒有人,當作0人計算吧!不過因為村民已經瘋了,人數也有可能是負的喔!?

當N和M都是0得的時候,代表所有世界的瑞男都成功逃離了,你就自己摸摸鼻子把你的程式停掉吧。

甚麼!你像知道你需要處理的數字範圍,那我就好心的告訴你吧!
你可以假設,
1≤N≤20000,0≤M≤60000,0≤u,v,x<N,0≤y<M,1≤k<231
任何時候村民數量都介於 -106 和 106 之間。
除了保證每條通到只會崩塌一次之外,
還有「瑞男飄移」跟「村民調度」的次數都不會超過250000次喔!
我、我可不是因為喜歡你...才、才告訴你的喔。

Output Format

對於每個世界,請輸出
Sekai i: ans
其中i代表世界的編號,ans代表瑞男平均電焦的人數,輸出四捨五入到小數點後六位。

Sample Input

3 3
10
20
30
0 1
1 2
0 2
D 2
Q 0 2
Q 1 1
D 1
Q 2 2
C 0 50
Q 0 1
E
3 3
10
20
20
0 1
1 2
0 2
Q 0 1
Q 0 2
Q 0 3
E
0 0

Sample Output

Sekai 1: 25.000000
Sekai 2: 16.666667

Hints

在瑞男逃出遺跡之後,遺跡因為承受不了黑魔法而崩塌了。
「妳...就是傳說中的編譯器嗎?」瑞男問身邊的少女。
「不...」少女低下頭。「我只是其中的8分之1喔,剩下的部份,已經忘記了呢~。」
黯黑摳頂界和周強.h的對決,愈來愈激烈了。

Problem Source

UVa 1479 by 果茶

Subtasks

No. Testdata Range Score
1 0~2 10
2 3~9 90

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 3000 65536 262144 2
4 3000 65536 262144 2
5 3000 65536 262144 2
6 3000 65536 262144 2
7 3000 65536 262144 2
8 3000 65536 262144 2
9 3000 65536 262144 2