2013 . 2017國手系列2：跑！
TopCoder
Description
傳說中，彥仁是一位能在競程界電爆全場的人，大家都稱他為「電人王」。然而，厲害的彥仁卻有一個天敵：蝴蝶。一旦蝴蝶出現在彥仁的身邊，他就得趕快跑走以避免被蝴蝶攻擊，形成奇觀之一：會跑的彥仁。
故事要從某一天彥仁來到了一個有許多蝴蝶的國家說起。這個國家有$N$個地區，從0編號到$N-1$，每個地區都有許多的蝴蝶棲息。一般來講，蝴蝶們是不會胡亂移動的，牠們終其一生會待在同一個地區，沒什麼攻擊性。然而，由於彥仁的到訪導致某種電場的變動，這個國家的蝴蝶開始出現一些異常的行為，例如說探索和遷移事件。
具體來說，「探索」是指某個地區$a$的蝴蝶可能會在任何時刻探索從該處到另一個地區$b$的「遷移路線」。探索的過程中，蝴蝶會沿途留下氣味，使得所有的蝴蝶都知道從$a$地區通往$b$地區有一條遷移路線。
蝴蝶為了避免迷路，它們的遷移路線會是單向的（也就是有起點和終點之分），並且每條遷移路線的終點都不同。另外，蝴蝶是很聰明的，他們探索的遷移路線絕對不會使得從一個地區能經由一些遷移路線飛回同一個地區，這樣就能確保不會有蝴蝶一直在某個圈子裡面飛不出來。
而「遷移」是指，某個地區$a$的部分蝴蝶開始沿著當前已經被探索的遷移路線飛行到其他的地區。蝴蝶們可能會連續飛過多條遷移路線，例如$a$地區到$b$地區有一條遷移路線、$b$地區到$c$地區有另一條，則$a$地區的蝴蝶遷移有可能會飛到$c$地區。注意因為這個國家的蝴蝶實在是太多了，所以同一個地區有可能會發生多次的遷移事件。
遷移中的蝴蝶對彥仁來說特別具有攻擊性。幸好彥仁有充足的消息來源，所以每當有一條新的遷移路線被探索出來，或者某個地方的蝴蝶開始遷移，彥仁都會收到消息。
請你寫一個程式，幫彥仁由這些消息判斷每一次蝴蝶遷移有沒有可能影響到他的所在地，以方便彥仁決定什麼時候要跑。
Input Format
本題沒有輸入，如果你輸入了任何東西可能會導致各種不可預期的結果(?)。
請#include "lib2013.h"之後實作下列三個函數。如果你的函數名稱不對或者長得不像下面那幾行，你將會獲得一個CE。
void init(int N);：評分程式會首先呼叫這個函數，並傳入地區總數量$N$。一開始沒有任何的遷移路線。
void explore(int a, int b);：蝴蝶們剛探索了一條從$a$地區到$b$地區的遷移路線。
int run(int a, int b);：$a$地區的蝴蝶開始遷移了！現在彥仁在$b$地區，如果彥仁有可能遇到遷移中的蝴蝶請回傳1，否則請回傳0。保證$a\neq b$。
注意：如果你在程式裡實作了main()函式，你也會獲得一個CE。
在同一次執行中，init只會被呼叫一次（也就是只有單筆測資）。
對於所有測資，$N\leq 10^ 6; Q\leq 2.5\times 10^ 6$，其中$Q$是呼叫run和explore的總次數。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0) | 每條遷移路線的起點都相同 | 1 |
| 2 (0~2) | 所有run的呼叫都在explore的呼叫之後 | 29 |
| 3 (3~5) | 呼叫explore的次數$\leq 100$； $N, Q\leq 5\times 10^ 5$ |
16 |
| 4 (6~8) | 每條遷移路線的起點都不同 | 32 |
| 5 (9~11) | 每條新探索的遷移路線的終點在當下不會是其他遷移路線的起終點 | 34 |
| 6 (12~15) | $N\leq 8000; Q \leq 2\times 10^ 4$ | 22 |
| 7 (12~21) | $N \leq 10^ 5;Q \leq 2.5\times 10^ 5$ | 51 |
| 8 (0~27) | 無 | 65 |
Output Format
本題沒有輸出，如果你輸出了任何東西，你將會獲得一個WA。
Sample Input 1
1 2 3
1 0 1
2 0 2
2 2 3
2 3 2
1 2 4
1 0 2
2 0 4
Sample Output 1
1
0
1
Sample Input 2
2 1 2
1 0 3
1 0 4
2 3 4
1 3 2
2 0 2
Sample Output 2
0
1
Hints
這裡有一個測試用的標頭檔，可以用來測試。
該標頭檔接受以下輸入，數字間皆以空白分隔：
第一行：$N, Q$；
接下來$Q$行：$t, a, b$，其中若$t=1$代表呼叫explore(a, b)、$t=2$代表呼叫run(a, b)。
測試程式將會輸出每次呼叫run的回傳值。
以下是一個保證格式正確（不會CE也不會RE、MLE）但只能讓你獲得1分的範例程式：
#include "lib2013.h" int s, q[1000000]; void init(int N) {} void explore(int a, int b) { s = a; q[b] = 1; } int run(int a, int b) { return s == a && q[b]; }
Problem Source
Problem Set / Description by Yihda Yol
建國中學106學年度校隊補選pD
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 0~2 | 29 |
| 3 | 3~5 | 16 |
| 4 | 6~8 | 32 |
| 5 | 9~11 | 34 |
| 6 | 12~15 | 22 |
| 7 | 12~21 | 51 |
| 8 | 0~27 | 65 |