g212: E.魔法集合(set)
Tags : DSU disjoint set
Accepted rate : 4人/4人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-09-17 20:37

Content

給定一個平面上的點所組成的集合S。這個集合有個特性假設:

1.若 (x1,y1)、(x1,y2)、(x2,y1都在集合內,則 (x2,y2也會自動被插入集合內。

2.S的初始狀態為空集合(意即初始集合大小為0)。

 

共給定 n 次操作,每次會將一個座標放進集合裡,請在每次操作後輸出集合大小。

請注意,有可能會放一個已經在集合內的座標,此情況下集合大小不變。

Input

輸入第一行有一個正整數 n ,代表將要插入的座標數量。

之後 n 行,每行有兩個用空格分隔的正整數 xi,yi,代表第次插入的座標為 (xi,yi)。

 

測資限制

1. 1<=n<=2e5。

2. 1<=xi,yi<=2e5。

Output

請輸出 n 行,每行有一個整數,第 i 行的整數代表經過第 i 次操作之後的集合大小。

Sample Input #1
4
1 1
1 2
2 1
2 2
Sample Output #1
1
2
4
4
Sample Input #2
6
1 1
2 2
1 2
3 3 
3 2
4 4
Sample Output #2
1
2
4
5
9
10
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <10M
公開 測資點#5 (5%): 1.0s , <10M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <10M
公開 測資點#8 (5%): 1.0s , <10M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <10M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
Hint :

 

範例1說明

操作1:插入(1,1)到集合中,此時集合大小為1。

操作2:插入(1,2)到集合中,此時集合大小為2。

操作3:插入(2,1)到集合中,由於(1,1)、(1,2)、(2,1)都已經在集合中,故(2,2)也會自動被插入集合,此時集合大小為4。

操作4:插入(2,2)到集合中,但(2,2)已經在集合中,故集合大小不變,仍為4。

 

範例2說明

 

操作1:插入(1,1)到集合中,此時集合大小為1。

操作2:插入(2,2)到集合中,此時集合大小為2。

操作3:插入(1,2)到集合中,由於(1,2)、(1,1)、(2,2)都已經在集合中,故(2,1)也會自動被插入集合,此時集合大小為4。

操作4:插入(3,3)到集合中,此時集合大小為5。

操作5:插入(3,2)到集合中,依字母順序會有下列變化:

      a.由於(3,3)、(3,2)、(2,2)都已經在集合中,故(2,3)也會自動被插入集合。

      同時,由於(2,1)、(2,2)、(3,2)都已經在集合中,故(3,1)也會自動被插入集合。

      b.由於(1,2)、(2,2)、(2,3)都已經在集合中,故(1,3)也會自動被插入集合;

故此時集合大小為9。

操作6:插入(4,4)到集合中,此時集合大小為10。

 

評分說明

本題共有四組子任務,每一組有多筆測試資料,條件如下所示:

1.  n<=50(20%)。

2. xi<=5(30%)。

3. n<=2000(20%)。

4. 無額外限制(30%)。

 
Tags:
DSU disjoint set
出處:
2021成功高中校內賽 [管理者:
CGSH (快加油吧~~)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」