內容
曾經有一部採訪影片《BBC 紀錄片：別和日本人談性 No Sex. We're Japanese.》在網路上流傳，其中有一段談到虛擬遊戲中的生活，不少男性以遊戲中的女角發生關係，其中以一款遊戲「Love Plus」為大宗，即使是擁有現實和虛擬的生活，若要選擇其中一方站，不少男性仍然「我選擇死亡」回答。
現在先不解決男女雙方的問題、在彼此關係上要如何運作，如何回到早些年沒有遊戲機、沒有網路、更沒有虛擬女友的交際生活，只有同性朋友要怎麼交流呢？於是有一場專門為這些男性舉行的一場交友會，規則如下所述：
- 一開始全場男性都彼此不認識
- 每一個男性分別喜歡各自的虛擬女友 (可以是同一個)
- 每一個時刻，其中兩個男性會因談論遊戲而成為朋友
- 自己朋友的朋友也會成為朋友
- 如果朋友的虛擬女友的類型不同，他們有可能會因偏好女友類型不同而爭吵，稱為不穩定對。
請問每一個時刻下，有多少穩定對朋友。
輸入說明
第一行會有一個 $ T $，表示接下來會有幾組測資。
每一組測資第一行會有兩個整數 $N, M$，表示會場有 $N$ 名男性以及會場會有 $M$ 個時刻。接下來會有一行 $N$ 個整數 $A_i$，表示第 $i$ 名男性的偏好虛擬女友類型。
接下來會有 $M$ 行，每一行上會有兩個整數 $x, y$，第 $i$ 行表示時刻 $i$ 男性 $x, y$ 成為朋友關係。
* $1 \le x, y, A_i \le N$
* $1 \le N, M \le 50000 $
每一組測資第一行會有兩個整數 $N, M$，表示會場有 $N$ 名男性以及會場會有 $M$ 個時刻。接下來會有一行 $N$ 個整數 $A_i$，表示第 $i$ 名男性的偏好虛擬女友類型。
接下來會有 $M$ 行，每一行上會有兩個整數 $x, y$，第 $i$ 行表示時刻 $i$ 男性 $x, y$ 成為朋友關係。
* $1 \le x, y, A_i \le N$
* $1 \le N, M \le 50000 $
輸出說明
對於每一個時刻，輸出穩定朋友對。
範例輸入
#1
2 3 2 1 2 1 1 2 2 3 4 4 1 2 2 1 1 2 2 3 1 3 2 4
範例輸出
#1
0 1 0 1 1 2
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (50%): 3.0s , <1M
公開 測資點#1 (30%): 3.0s , <1M
公開 測資點#2 (10%): 3.0s , <1M
公開 測資點#3 (10%): 3.0s , <10M
公開 測資點#0 (50%): 3.0s , <1M
公開 測資點#1 (30%): 3.0s , <1M
公開 測資點#2 (10%): 3.0s , <1M
公開 測資點#3 (10%): 3.0s , <10M
提示 ：
第一組測資
- 時刻 1，沒有任何一組。
- 時刻 2，(1, 3) 是一組穩定對，因為他們都喜歡類型 1 的。
第二組測資
- 時刻 1，沒有任何一組。
- 時刻 2，(2, 3) 是一組穩定對。
- 時刻 3，(2, 3) 是一組穩定對。
- 時刻 4，(2, 3) 和 (1, 4) 是一組穩定對。
標籤:
出處:
IPSC2015
[管理者：
morris1028
(碼畜)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||