Login with GitHub. Nope?
修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm NeoHOJ 強勢復活中 (Open beta)
Submit  Ranklist

Problem : 343 - pC.老鼠愛大米

Problem Statistics

Solved Member: 21  Submission: 82  User Tried: 27

Statement:

附中的老鼠們平常生活在一個複雜的地道系統中! 這個系統中有N個老鼠窩跟M條單向的地道(為了避免卡住,老鼠們的世界也是有秩序的),每個老鼠窩都住著很多隻老鼠,我們將鼠窩編號為1~N,每條單向地道連接兩個老鼠窩。兩個老鼠窩之間可能不只有一條地道,也可能地道的起點和終點是同一個老鼠窩。
其中編號K的老鼠窩有很多很多的大米,大米的擁有者——老鼠威廷,死前說了這麼一段話:「想要我的大米嗎?如果想要的話那就到我的老鼠窩吧,我全都放在那裡了!」,於是附中的老鼠們爭相前往探險,便開啟了大地道時代。
由於老鼠們不確定自己的鼠窩有沒有辦法到達編號K的鼠窩,他們請你幫忙寫程式計算共有幾隻老鼠有辦法找到大米。

Input:Output:

第1行有三個正整數N, M, K,表示有N個老鼠窩,M條單向地道,以及大米位在編號K的老鼠窩。
第2~M+1行,每行有兩個正整數a, b,表示有一條單向地道從a連向b。
第M+2行有N個非負整數,依序代表編號1~N的老鼠窩有多少老鼠。
一個正整數表示有多少老鼠可以走到編號為K的老鼠窩。

Sample Input:Sample Output:

5 5 3
1 2
2 1
3 1
4 3
2 3
7 8 6 2 7
23

HINT:

占總分30%的資料,滿足: N<=500 M<=1,000
占總分60%的資料,滿足: N<=1,000 M<=4,000
全部的資料滿足以下條件:
1<= N <=100,000
1<= M<=500,000
1<= K <= N
0<= 一個鼠窩內的老鼠數量 <= 100

Source:

103附中校內賽

Problem Setter

Testdata:

TestTimeMemoryScore
01000ms262144kb
1-11000ms262144kb30
1-21000ms262144kb
2-11000ms262144kb30
2-21000ms262144kb
3-11000ms262144kb40
3-21000ms262144kb
3-31000ms262144kb