2013 . 2017國手系列2：跑！

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

alphabeta

User's AC Ratio

67.9% (19/28)

Submission's AC Ratio

27.8% (83/299)

Tags

CKcon 2018-CKcon-sup IOIstyle graph-traversal doubling data-structures

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≠b。

注意：如果你在程式裡實作了main()函式，你也會獲得一個CE。
在同一次執行中，init只會被呼叫一次（也就是只有單筆測資）。

對於所有測資，N≤106;Q≤2.5×106，其中Q是呼叫run和explore的總次數。

子任務（測資） 額外限制 分數
1 (0) 每條遷移路線的起點都相同 1
2 (0~2) 所有run的呼叫都在explore的呼叫之後 29
3 (3~5) 呼叫explore的次數≤100；
N,Q≤5×105		 16
4 (6~8) 每條遷移路線的起點都不同 32
5 (9~11) 每條新探索的遷移路線的終點在當下不會是其他遷移路線的起終點 34
6 (12~15) N≤8000;Q≤2×104 22
7 (12~21) N≤105;Q≤2.5×105 51
8 (0~27) 無 65

Output Format

本題沒有輸出，如果你輸出了任何東西，你將會獲得一個WA。

Sample Input 1

5 8
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

0
1
0
1

Sample Input 2

5 6
2 1 2
1 0 3
1 0 4
2 3 4
1 3 2
2 0 2

Sample Output 2

0
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 7666 262144 262144 1 2 8
1 7666 262144 262144 2 8
2 7666 262144 262144 2 8
3 7666 262144 262144 3 8
4 7666 262144 262144 3 8
5 7666 262144 262144 3 8
6 7666 262144 262144 4 8
7 7666 262144 262144 4 8
8 7666 262144 262144 4 8
9 7666 262144 262144 5 8
10 7666 262144 262144 5 8
11 7666 262144 262144 5 8
12 7666 262144 262144 6 7 8
13 7666 262144 262144 6 7 8
14 7666 262144 262144 6 7 8
15 7666 262144 262144 6 7 8
16 7666 262144 262144 7 8
17 7666 262144 262144 7 8
18 7666 262144 262144 7 8
19 7666 262144 262144 7 8
20 7666 262144 262144 7 8
21 7666 262144 262144 7 8
22 7666 262144 262144 8
23 7666 262144 262144 8
24 7666 262144 262144 8
25 7666 262144 262144 8
26 7666 262144 262144 8
27 7666 262144 262144 8
Submit
Back to Top