http://agc016.contest.atcoder.jp/tasks/agc016_d
うーん。Union Find見えてからが遅かった。EFもようわからん
連結成分を考えれば良くて、変更前の数列のxorの値と変更後の数列のxorの値が等しいか異なるかで場合分け。
答えは(連結成分の数)+(異なる値の数)-1とかになる。場合分けで多少異なるが。なので適当にUnion Findして連結成分の数を求める。
答えが上の式に本当になるかはオイラーグラフを使って考える。
変更前の数列Ai(1<=i<=N)がAi=X1→X2→…Xr=Biになったとして、
X1→X2, X2→X3…と辺を張っていくと、b0からa0へのオイラーグラフ(一筆書きできるグラフ)となる。
そのオイラーグラフを逆からたどっていくとswapすべき値がわかる。
なので、ai→biの条件を満たしつつ、辺が最小で済むようにオイラーグラフを作ることが目標となる。
連結成分がC個あるとそれらをつないでオイラーグラフにするためにはC-1本多く辺を足せばよい。
int par[MAX_N]; int ran[MAX_N]; void init(int n) { for(int i = 0; i < n; i++) { par[i] = i; ran[i] = 0; } } int find(int x) { if(par[x] == x) { return x; } else return par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if(x == y) return; if(ran[x] < ran[y]) { par[x] = y; } else { par[y] = x; if(ran[x] == ran[y]) ran[x]++; } } bool same(int x, int y) { return find(x) == find(y); } int N; int AA[MAX_N]; int BB[MAX_N]; int A[MAX_N], B[MAX_N]; int C[MAX_N]; vector<int> vec; int fd(int a) { return lower_bound(all(vec), a) - vec.begin(); } void solve() { cin >> N; int a = 0; rep(i, 0, N) { cin >> AA[i]; a ^= AA[i]; } rep(i, 0, N) cin >> BB[i]; int at = 0; rep(i, 0, N) { if(AA[i] != BB[i]) { A[at] = AA[i]; B[at] = BB[i]; at++; } } N = at; A[N] = a; rep(i, 0, N) vec.push_back(B[i]); sort(all(vec)); vec.erase(unique(all(vec)), vec.end()); int n = (int)vec.size(); rep(i, 0, N) { int a = fd(B[i]); C[a]++; } bool ok = true; rep(i, 0, N + 1) { int a = fd(A[i]); if(a >= n) continue; if(vec[a] == A[i]) C[a]--; } rep(i, 0, n) { if(C[i] > 0) { ok = false; break; } } if(!ok) cout << "-1\n"; else { init(n); rep(i, 0, N) unite(fd(A[i]), fd(B[i])); set<int> s; rep(i, 0, n) s.insert(find(i)); if(fd(A[N]) < n && vec[fd(A[N])] == A[N]) cout << N + (int)s.size() - 1 << "\n"; else cout << N + (int)s.size() << "\n"; } }