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
hanhan0912 Testdata:
Test | Time | Memory | Score |
---|
0-1 | 1000ms | 262144kb | |
0-2 | 1000ms | 262144kb | |
1-1 | 1000ms | 262144kb | 49 |
1-2 | 1000ms | 262144kb | |
1-3 | 1000ms | 262144kb | |
1-4 | 1000ms | 262144kb | |
1-5 | 1000ms | 262144kb | |
1-6 | 1000ms | 262144kb | |
1-7 | 1000ms | 262144kb | |
1-8 | 1000ms | 262144kb | |
1-9 | 1000ms | 262144kb | |
2-1 | 2000ms | 262144kb | 20 |
2-2 | 2000ms | 262144kb | |
2-3 | 2000ms | 262144kb | |
2-4 | 2000ms | 262144kb | |
2-5 | 2000ms | 262144kb | |
2-6 | 2000ms | 262144kb | |
2-7 | 2000ms | 262144kb | |
2-8 | 2000ms | 262144kb | |
2-9 | 2000ms | 262144kb | |
2-10 | 2000ms | 262144kb | |
2-11 | 2000ms | 262144kb | |
2-12 | 2000ms | 262144kb | |
2-13 | 2000ms | 262144kb | |
2-14 | 2000ms | 262144kb | |
3-1 | 2000ms | 262144kb | 31 |
3-2 | 2000ms | 262144kb | |
3-3 | 2000ms | 262144kb | |
3-4 | 2000ms | 262144kb | |
3-5 | 2000ms | 262144kb | |
3-6 | 2000ms | 262144kb | |
3-7 | 2000ms | 262144kb | |
3-8 | 2000ms | 262144kb | |
3-9 | 2000ms | 262144kb | |
3-10 | 2000ms | 262144kb | |
3-11 | 2000ms | 262144kb | |
3-12 | 2000ms | 262144kb | |
3-13 | 2000ms | 262144kb | |
3-14 | 2000ms | 262144kb | |