TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

90.5% (19/21)

Submission's AC Ratio

23.3% (47/202)

Tags

Description

傳說中,土撥鼠是一種神奇的動物,牠們不只會挖地道、會飛,還會電人。

但是會飛的土撥鼠太難追蹤了,而電人的土撥鼠會把你電爆,所以我們只考慮挖地道的土撥鼠。

現在有N個土撥鼠巢穴,從0編號到N-1,但是沒有任何的地道。土撥鼠可能會挖出一些雙向通行的地道,挖好的地道也有可能會崩塌。

所以你想要知道在某個時間點,如果選一些巢穴監視,裡面有沒有可能有一些土撥鼠可以透過地道,跑到你沒有選到的巢穴躲避你的監視。

Input Format

第一行有兩個整數N、M,代表有N個巢穴、M筆操作。

接下來M行,每行有一個操作。
如果是0 A B,代表土撥鼠挖出了一條新的A, B間的地道。
如果是1 A B,代表A, B間的其中一條地道崩塌,土撥鼠不能再從這條地道通過。
如果是2 K A1 A2 ... AK,代表詢問這個時間點,是否有任何地道從這些巢穴通往其它的巢穴。

保證地道崩塌之前一定存在這條地道,一筆查詢中所有的點不會重複,且一組起終點相同的地道不會超過1000條。注意可能有A, A間的地道。

以下的S代表所有詢問中K的總和,E代表過程中最多會有幾條地道。
對於5%的測資,$ N \leq 10; M, S \leq 100 $。
對於5%的測資,$ N \leq 30; M, S \leq 250 $。
對於5%的測資,$ N \leq 100; M, S \leq 2 \times 10^ 4 $。
對於10%的測資,$ N \leq 100; M \leq 3 \times 10^ 4 ; S \leq 10^ 5; E \leq 5000 $。
對於15%的測資,$ N \leq 1000; M, S \leq 6 \times 10^ 5; E \leq 2 \times 10^ 5 $。
對於20%的測資,$ N \leq 3000 $。
對於20%的測資,$ N \leq 10^ 5; M, S \leq 5 \times 10^ 6 $。
對於所有的測資,$ N \leq 5 \times 10^ 5; M, S \leq 10^ 7; E \leq 7 \times 10^ 5 $。

Output Format

對於每一筆詢問,如果不存在通往其它巢穴的地道,輸出一行1,否則輸出一行0。

Sample Input

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

Sample Output

1
1
0
1

Hints

測資很大,所以請不要使用完全不優化的cin/cout。

Problem Source

NT

Subtasks

No. Testdata Range Score
1 0~1 5
2 2~3 5
3 4~5 5
4 6~7 10
5 8~9 15
6 10~12 20
7 13 20
8 14~15 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 102400 262144 1
1 1000 102400 262144 1
2 1000 102400 262144 2
3 1000 102400 262144 2
4 1000 102400 262144 3
5 1000 102400 262144 3
6 1000 102400 262144 4
7 1000 102400 262144 4
8 1000 102400 262144 5
9 1000 102400 262144 5
10 5000 102400 262144 6
11 7000 102400 262144 6
12 7000 102400 262144 6
13 5000 102400 262144 7
14 7000 102400 262144 8
15 7000 102400 262144 8