読者です 読者をやめる 読者になる 読者になる

誤読

文字通りくそコード

CF 776D - The Door Problem

コンテスト中にACできなかった、悲しい

ツイッターで思いっきり嘘解法を述べてしまった

lockを2回介してもUniteできるので、unite出来なくなるまで無限に回す(不安)

最初、ライツアウトだし方程式立ててガウスジョルダンで常勝wwwwwってやってたけど10^10だった

ガウスジョルダンを自前で書きたいので今度書く

signed main() {

	int n, m;
	scanf("%d %d", &n, &m);
	vector<int> door(n);
	REP(i, n) {
		scanf("%d", &door[i]);
	}
	UnionFind uf(m + 2);
	vector<vector<int>> fs(n);
	vector<pair<int, vector<int>>> sw;
	int k;
	REP(i, m) {
		scanf("%d", &k);
		vector<int> lt;
		REP(j, k) {
			int a;
			scanf("%d", &a);
			a--;
			fs[a].push_back(i);
			if (!door[a])
				lt.push_back(a);
		}
		sw.push_back({ i,lt });
	}
	REP(i, n) {
		if (door[i]) {
			uf.unionSet(fs[i][0], fs[i][1]);
		}
	}

	bool f = 1;
	while (f) {
		map<int, set<int>> kanset;
		f = 0;
		for (auto itr : sw) {
			for (auto itr2 : itr.second) {
				if (!door[itr2]) {
					for (auto itr3 : fs[itr2]) {
						if (itr3 != itr.first)
							kanset[uf.root(itr3)].insert(uf.root(itr.first));
					}
				}
			}
		}
		for (auto itr : kanset) {
			if (!itr.second.empty()) {
				int to = *itr.second.begin();
				for (auto itr2 : itr.second) {
					if (!uf.findSet(to, itr2))
						f = 1;
					uf.unionSet(to, itr2);
				}
			}
		}
	}
	REP(i, n) {
		if (!door[i]) {
			if (uf.findSet(fs[i][0], fs[i][1])) {
				printf("NO\n");
				return 0;
			}

		}
	}
	printf("YES\n");
	return 0;
}