結果
問題 | No.2089 置換の符号 |
ユーザー |
👑 ![]() |
提出日時 | 2022-09-30 21:37:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 756 bytes |
コンパイル時間 | 387 ms |
コンパイル使用メモリ | 82,236 KB |
実行使用メモリ | 76,548 KB |
最終ジャッジ日時 | 2024-12-22 22:41:34 |
合計ジャッジ時間 | 2,946 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
""""""import sysdef uf_find(n,p):ufl = []while p[n] != n:ufl.append(n)n = p[n]for i in ufl:p[i] = nreturn ndef uf_union(a,b,p,rank):ap = uf_find(a,p)bp = uf_find(b,p)if ap == bp:return Trueelse:if rank[ap] > rank[bp]:p[bp] = apelif rank[ap] < rank[bp]:p[ap] = bpelse:p[bp] = aprank[ap] += 1return FalseN = int(input())A = list(map(int,input().split()))p = [i for i in range(N)]rank = [0] * Nfor i in range(N):uf_union(i,A[i]-1,p,rank)ans = Nfor i in range(N):if uf_find(i,p) == i:ans -= 1if ans % 2 == 1:print (-1)else:print (1)