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

Problem : 261 - Garden

Problem Statistics

Solved Member: 9  Submission: 96  User Tried: 13

Statement:

植物學家Somhed經常帶領數群學生們一起前往泰國最大的熱帶花園。此花園的景色是由N 個噴泉(編號為0、1、2、…⋯、N-1)和 M 個步道組成。每一條步道連接兩個相異的噴泉,並且可以依照任意方向進行遊覽。每一個噴泉皆可以由至少一條步道離開。這些步道上皆有Somhed希望觀賞的美麗熱帶植物。每一群學生可以由任何一個噴泉開始他們的行程。

Somhed熱愛美麗的熱帶植物,因此,在任何噴泉時,他和他的學生總會選擇最美麗且可以離開該噴泉的步道,除非其為剛剛走過的步道(僅考慮上一步的移動)並且還有其他的替代步道,在此種狀況下,他們就會選擇第二美麗的步道作為替代方案。當然,如果沒有任何替代方案時,他們會循著相同的步道往回走。注意,由於Somhed是專業的植物學家,對他而言,沒有任何兩條步道是一樣美麗的。

他的學生對於植物並不十分感興趣。然而,他們非常希望可以在噴泉 P 旁的高檔餐廳享用午餐。Somhed知道他的學生們在走過剛好 K 條步道後就會肚子餓,而且每一群學生都有不同的 K 值。在這樣的前提下,Somhed想知道在滿足下列的條件下,各有多少不同的路徑可以選擇給每一群學生:

 • 每一群學生可以由任何一個噴泉出發;
 • 接續步道的決定,必須依照上述的方法;
 • 每一群學生必須在剛好行走 K 條步道後到達編號為 P 的噴泉。

注意:學生們可能會在路徑中提早經過噴泉 P,但是他們仍然需要在噴泉 P 完成他們的路徑。

Task:

給定噴泉和步道的資訊,你必須針對 Q 群學生各自的 K 值,找到正確的答案。

 • N – 噴泉的數目。這些噴泉的編號為 0 至 N-1。
 • M – 步道的數目。這些步道的編號為 0 至 M-1。其編號大小和其美麗程度相反。對於 0 ≤ i < M-1,步道 i 比步道 i+1 美麗。
 • P – 高檔餐廳所在地之噴泉
 • Q – 學生群的數目。
 • Gi –代表第 i 群學生所行走的步道數目( K )。

你的程式必須找到所有可能的路徑數目,讓第i群學生可以剛好在走過Gi 條步道後抵達噴泉 P。

對於每一群學生,你的程式必須輸出一個數字X於一行,表示路徑的數目為 X。

這些答案必須依照和學生群編號相同的順序回答。如果沒有任何合法的路徑,你的程式必須輸出0。

Input:Output:

第一行有三個數字N M P。

接下來有M行,每行兩個數字,表示每條步道所連接的相異噴泉。

接下來的一行是數字Q,表示學生群的數目。

接下來的一行有Q個以空白隔開的數字Gi。
對於每一群學生,你的程式必須輸出一個數字X於一行,表示路徑的數目為 X。

這些答案必須依照和學生群編號相同的順序回答。如果沒有任何合法的路徑,你的程式必須輸出0。

Subtask 1 (49 points)
 •2 ≤ N ≤ 1000
 •1 ≤ M ≤ 10000
 •Q = 1
 •1 ≤ Gi ≤ 100
Subtask 2 (20 points)
 •2 ≤ N ≤ 150000
 •1 ≤ M ≤ 150000
 •Q = 1
 •1 ≤ Gi ≤ 1000000000
Subtask 3 (31 points)
 •2 ≤ N ≤ 150000
 •1 ≤ M ≤ 150000
 •1 ≤ Q ≤ 2000
 •1 ≤ Gi ≤ 1000000000

Sample Input:Sample Output:

Sample #1:
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3

Sample #2:
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
Sample #1:
2

Sample #2:
1
2

HINT:



測資3d, 3f, 3g時限放寬為10s @ 2013/5/27 16:39 by hanhan0912
子測資3時限縮短為2s @ 2013/7/24 23:56 by hanhan0912

Source:

IOI 2011

Problem Setter

Testdata:

TestTimeMemoryScore
0-11000ms262144kb
0-21000ms262144kb
1-11000ms262144kb49
1-21000ms262144kb
1-31000ms262144kb
1-41000ms262144kb
1-51000ms262144kb
1-61000ms262144kb
1-71000ms262144kb
1-81000ms262144kb
1-91000ms262144kb
2-12000ms262144kb20
2-22000ms262144kb
2-32000ms262144kb
2-42000ms262144kb
2-52000ms262144kb
2-62000ms262144kb
2-72000ms262144kb
2-82000ms262144kb
2-92000ms262144kb
2-102000ms262144kb
2-112000ms262144kb
2-122000ms262144kb
2-132000ms262144kb
2-142000ms262144kb
3-12000ms262144kb31
3-22000ms262144kb
3-32000ms262144kb
3-42000ms262144kb
3-52000ms262144kb
3-62000ms262144kb
3-72000ms262144kb
3-82000ms262144kb
3-92000ms262144kb
3-102000ms262144kb
3-112000ms262144kb
3-122000ms262144kb
3-132000ms262144kb
3-142000ms262144kb