ABC155 F - Perils in Parallel

atcoder.jp

面白れー問題

解法

この問題は、全てのスイッチを0にする問題と、xorでスイッチの階差を取った時に全ての値を0にする問題が等しい。
この時、区間内の全ての要素を反転する処理は左端と右端を反転させる処理になる。この処理が でできるようになった。

ノード (階差を取った後のノード) に関係するスイッチを辺にする。
を反転させようとすると、もうひとつのノード が反転するような辺のことである。

これをつなげてグラフにした時、各連結成分のもともとの1の数が奇数だと全てを0にできない。
なぜなら、1の数は2個ずつ減っていくことしか出来ないので、最終的に一つ1が残ってしまう。

1の数が偶数の場合は、グラフを適当な全域木にしてルートノードに1を伝播させていくと、消えてくれるので、0にできる。

構成するにはこのような処理をシミュレーションすればできます。

Source

int main() {
	int N, M; cin >> N >> M;
	vector<Pi> bomb(N); cin >> bomb;
	vint sa(N+1);
	vector<Pi> dat(M); cin >> dat;
	vector<vector<Pi>> G(N+1);
	vint ans(M, 0);

	sort(begin(bomb), end(bomb));

	sa[0] = bomb[0].second, sa[N] = bomb[N-1].second;
	for (int i = 1; i < N; i++) sa[i] = (bomb[i].second ^ bomb[i-1].second);

	for (int i = 0; i < M; i++) {
		auto &v = dat[i];
		int l = v.first, r = v.second;
		int posl = lower_bound(begin(bomb), end(bomb), Pi(l, -INF)) - begin(bomb);
		int posr = upper_bound(begin(bomb), end(bomb), Pi(r, INF)) - begin(bomb);
		v.first = posl, v.second = posr;
		if (posl == posr) continue;
		G[posl].emplace_back(posr, i);
		G[posr].emplace_back(posl, i);
	}
	
	vector<bool> flag(N+1);
	function<bool(int, int)> dfs = [&](int u, int index) -> bool {
		if (flag[u]) return (false);
		flag[u] = true;
		for (auto &v : G[u]) dfs(v.first, v.second);

		if (sa[u] == 1) {
			if (index == -1) return (true);
			int a = dat[index].first, b = dat[index].second;
			sa[a] = 1 - sa[a], sa[b] = 1 - sa[b];
			ans[index] = 1;
		}
		return (false);
	};

	for (int i = 0; i <= N; i++) {
		if (dfs(i, -1)) {
			cout << -1 << endl;
			return (0);
		}
	}
	
	vint ansd;
	for (int i = 0; i < M; i++) {
		if (ans[i]) ansd.push_back(i+1);
	}
	cout << ansd.size() << endl;
	
	if (ansd.size() == 0) { cout << endl; return (0); }
	cout << ansd[0];
	for (int i = 1; i < ansd.size(); i++) cout << " " << ansd[i];
	cout << endl;
	return (0);
}

感想

面白いので解けるようにしておきたいなあ