f310: 10158 - War
Tags : DSU
Accepted rate : 3人/5人 ( 60% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-10-17 13:05

Content

給定 N 個人( 編號為 0, 1, 2,..., N-1 )和 4 種操作方式,模擬一系列的操作並輸出過程中的結果。

只有一筆測資,指令的形式一定是 c X Y ,c 代表類型,X Y 代表不同編號的人員且保證 0 ≦ X, Y < N 。

操作的指令以 0 0 0 作為該次輸入的結尾,人數限制 N < 10,000。

操作方式:

     c = 1, setFriends( X, Y )   設定 X, Y 為朋友關係 ( 屬於同個國家 )

     c = 2, setEnemies( X, Y )  設定X, Y 為敵對關係 ( 屬於不同國家 )

     c = 3, areFriends( X, Y )   確認 X, Y 是否為朋友關係?

     c = 4, areEnemies( X, Y )  確認 X, Y 是否為敵對關係?

      前兩個操作 setFriends( X, Y ) / setEnemies( X, Y ) 設定關係時如果存在矛盾時則該次設定無效 且 輸出 -1 作為代表。 

      後兩個操作 areFriends( X, Y ) / areEnemies( X, Y ) 時若 X Y 關係「不清楚」(設定並未提到)一樣是輸出 0。 

關係皆具有下列7項性質,符號說明:A~B代表AB為朋友關係而A*B代表AB為敵對關係。

      1. 朋友的朋友也是朋友: If x ~ y and y ~ z then x ~ z

      2. 敵人的敵人會是朋友: If x * y and y * z then x ~ z 

      3. 朋友的敵人也是敵人:If x ~ y and y * z then x * z 

      4. 朋友關係為相互性    :If x ~ y then y ~ x      

      5. 敵對關係為相互性   : If x * y then y * x

      6. 自己和自己一定是朋友關係:x ~ x 

      7.  自己和自己一定不是敵對關係:Not x * x 

關係一定但設定後為永久性質,發生矛盾時則順序越後面設定的關係則視為無效。

Input

給定 N 個人和題目定義的 4 種類型操作方式

Output

輸出對應的結果。

設定時發生矛盾時該次指令會輸出 -1 。

確認關係時則該行輸出結果。

Sample Input #1
10
1 0 1
1 1 2
2 0 5
3 0 2
3 8 9
4 1 5
4 1 2
4 8 9
1 8 9
1 5 2
3 5 2
0 0 0
Sample Output #1
1
0
1
0
0
-1
0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1K
Hint :

Disjiont Set Union

Tags:
DSU
出處:
UVA-10158 [管理者:
rollfc (胖胖貓)
]


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