[白俊1043]うそをつく

11577 ワード
boj テキストリンク
質問する
  • 白駿1043
    • を選択します.
  • 実施
  • ブルートフォース
    • に答える
    時間の複雑さはよくわかりませんが、O(NM^2)では必ず終わると思いますが、N、Mは50以下の自然数なので、実施問題だけです.
    Mパーティーを巡回し、真相を知る人がいるチームの全メンバーを集合中に置き、他のメンバーが集合に入らないまで次のチームに集合中のメンバーがいるかどうかを繰り返しチェックする.
    コード#コード#
    #include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, m, k;
set<int> s;
vector<int> v[51];
vector<bool> check(51, true);


int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++) {
		int a;
		cin >> a;
		s.insert(a);
	}

	for (int i = 0; i < m; i++) {
		int x,t; cin >> t;
		while (t--) {
			cin >> x;
			v[i].push_back(x);
		}
	}

	while (true) {
		bool c = false;

		for (int i = 0; i < m; i++) {
			bool C = false;
			for (int j = 0; j < v[i].size(); j++) {
				if (check[i] && s.count(v[i][j]) != 0) {
					check[i] = false;
					C = true;
					break;
				}
			}
			if (C) {
				c = true;
				for (int j = 0; j < v[i].size(); j++) {
					s.insert(v[i][j]);
				}
			}
		}

		if (!c) break;
	}

	int ans = 0;
	for (int i = 0; i < m; i++) if (check[i]) ans++;
	cout << ans;




	return 0;
}
    プロジェクトがグローバル一意のidプライマリ・キーを生成する方法
    クエリ速度の最適化に関するいくつかの経験