「玲思」──一種傳說中具有神秘力量的物品,只要將它正確組裝,就能獲得大量的寶藏。
玲思在未組裝前看起來只是一堆圓環,可以拆開、也可以組合。任何一個圓環可以接上任意數量的圓環。
為了瞭解玲思運作的原理,我們先定義圓環組裝的基本結構:圓環鍊。一條圓環鍊定義為n(≥1)個圓環頭尾相接構成的結構。例如下圖便是一個圓環鍊。
很明顯地,在n≥2的情況,除了頭尾的兩個圓環只與另一個圓環相接,其餘所有的圓環都與另外兩個圓環相接。當然,n=1的情況,也就是只有一個圓環,也算是圓環鍊。
當然,玲思沒有那麼容易組裝,因為可以構成各種複雜的結構。然而,有一個人們研究玲思時常用的指標,即「特殊圓環」的數量。
我們知道,如果玲斯上任何一個圓環消失,將導致玲思的結構改變。對於玲思上的每一個圓環,如果那個圓環消失後,剩下的所有的環構成很多個圓環鍊,則稱該圓環為一個「特殊圓環」。
例如上圖,編號2和編號3的圓環都是特殊圓環,然而編號0, 1, 4, 5, 6都不是。
現在,玲思的所有圓環都是分開的。喵喵想要透過把一次一次把兩個環接起來的方式,完成玲思。然而,為了順利完成,他希望能隨時隨地查詢特殊圓環的數量。因此,你的任務就是紀錄他把那些圓環接起來,並隨時應付他的查詢。
本題沒有輸入,如果你輸入了任何東西可能會導致各種不可預期的結果(?)。
請#include "lib1270.h"
之後實作下列三個函數。如果你的函數名稱不對或者長得不像下面那些行,你將會獲得一個CE。
void Init(int);
void Link(int, int);
int CountCritical();
第一個函數傳入一個值N,代表玲思有幾個環,會在一次組裝的開始呼叫。
第二個函數傳入兩個值A、B,代表喵喵要把A、B兩個環接起來。
第三個函數代表喵喵想要知道特殊圓環的數量,必須回傳對應的答案。
在一次執行當中,喵喵會想要嘗試組裝很多次玲思,所以請確保函數中有進行初始化。
以下敘述以L代表呼叫Link
的次數,以P代表呼叫CountCritical
的次數。
對於20%的測資,N ≤ 5,000,L ≤ 5,000,P = 1;唯一的一次CountCritical
必在所有Link
之後呼叫。
對於17%的測資,N ≤ 1,000,000,L ≤ 1,000,000,P = 1;唯一的一次CountCritical
必在所有Link
之後呼叫。
對於18%的測資,N ≤ 20,000,L ≤ 10,000,P = 100。
對於14%的測資,N ≤ 100,000,L + P ≤ 100,000。
對於所有的測資,N ≤ 1,000,000,L + P ≤ 1,000,000。
本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA。
這裡有一個測試用的標頭檔,可以用來測試。
IOI 2012 Day 1
Judge / Description by Yihda Yol
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 20 |
2 | 1 | 17 |
3 | 2 | 18 |
4 | 3 | 14 |
5 | 4 | 31 |