結果
問題 | No.2089 置換の符号 |
ユーザー |
|
提出日時 | 2022-09-30 21:46:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,757 bytes |
コンパイル時間 | 2,056 ms |
コンパイル使用メモリ | 200,944 KB |
最終ジャッジ日時 | 2025-02-07 19:21:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using vi = vector<int>;using vl = vector<ll>;using pi = pair<int,int>;using pl = pair<ll,ll>;#define all(x) x.begin(),x.end()#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)const long long MOD = 1000000007;const long long MOD2 = 998244353;const int INF = ((1<<30)-1);const long long LINF = (1LL<<60);const double PI = 3.141592653589793238;template<class T> inline void chmax(T& a, T b) {if (a < b) {a = b;}}template<class T> inline void chmin(T& a, T b) {if (a > b) {a = b;}}class UnionFind{private:vector<ll> p;vector<ll> rank;public:UnionFind(ll n){p.resize(n,-1);rank.resize(n,1);}ll find(ll x){if(p[x]<0)return x;return p[x]=find(p[x]);}void unite(ll x,ll y){x = find(x);y = find(y);if(x == y)return;if(rank[x] > rank[y])swap(x,y);if(rank[x] == rank[y])rank[y]++;p[y] += p[x];p[x] = y;}ll size(ll x){return -p[find(x)];}bool same(ll x, ll y){return find(x) == find(y);}};int solve(){int n; cin >> n;vi a(n);rep(i,0,n)cin >> a[i];UnionFind uf(n);rep(i,0,n){--a[i];uf.unite(i , a[i]);}int ans = 0;rep(i,0,n){if(uf.find(i) != i)continue;ans += uf.size(i)-1;}if(ans % 2 == 0)cout << 1 << endl;else cout << -1 << endl;return 0;}int main(){cout << fixed << setprecision(10);ios::sync_with_stdio(0), cin.tie(0);int t = 1;//cin >> t;for(int i = 0; i < t; i++){solve();}return 0;}