#795498 (C++17) No.2178 Payable Magic Items

• 問題: No.2178 Payable Magic Items
• ユーザー: MasKoaTS
• 提出日時: 2022-09-04 17:41:38
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 975 bytes
• コンパイル時間: 870 ms
• コンパイル使用メモリ: 79,772 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-05-08 13:16:07
• 合計ジャッジ時間: 3,031 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	3 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	WA	-
testcase_08	AC	2 ms; 5,376 KB
testcase_09	WA	-
testcase_10	RE	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	RE	-
testcase_21	AC	3 ms; 5,376 KB
testcase_22	WA	-
testcase_23	RE	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-

ソースコード

#include <iostream>
#include <vector>
#define rep(i, l, n) for (int i = (l); i < (n); i++)
using namespace std;
template <class T>	using V = vector<T>;

int toNum(string s) {
	int ret = 0;
	rep(i, 0, s.size()) {
		char c = s[i];
		ret |= (3 - (c - 'A')) << (i << 1);
	}
	return ret;
}


int main(void) {
	int N, K;	cin >> N >> K;
	V<int> mag(N);
	rep(i, 0, N) {
		string s;	cin >> s;
		mag[i] = toNum(s);
	}

	V<bool> visited(1 << (K << 1));
	for (int sv : mag) {
		if (visited[sv] == true) {
			continue;
		}
		V<int> stk = { sv };
		while (stk.empty() == false) {
			int v = stk[stk.size() - 1];
			stk.pop_back();
			rep(i, 0, K) {
				int k = i << 1;
				if (((v >> k) & 3) == 0) {
					continue;
				}
				int nv = v - (1 << k);
				if (visited[nv] == true) {
					continue;
				}
				visited[nv] = true;
				stk.push_back(nv);
			}
		}
	}

	int ans = 0;
	for (int v : mag) {
		if (visited[v] == false) {
			continue;
		}
		ans++;
	}
	cout << ans << endl;

	return 0;
}