AGC_016D: XOR Replace

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";
	}
}