Submission #1207431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207431		Trn115	지도 색칠하기 (GA3_map)	C++20	85 / 120	1594 ms	416 KiB

map

#include <bits/stdc++.h>

using namespace std;

inline int getbit(int x, int i) {
	return (x >> (i - 1)) & 1;
}

long long NumberOfMaps (signed N, signed M, signed *A, signed *B) {
	vector<vector<int>> g(N + 1);
	for (int i = 0; i < M; ++i) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}

	int si = 1 << N, mask;
	long long res = 0;
	vector<int> color;

	bool sat[2];
	function<void(int, int, int)> dfs = [&](int v, int c, int type) {
		color[v] = c;
		for (int u : g[v]) {
			if (getbit(mask, u) != type) continue;
			if (color[u] == -1) {
				dfs(u, c ^ 1, type);
			} else if (color[u] == c) {
				sat[type] = false;
			}
		}
	};

	for (mask = 0; mask < si; ++mask) {
		color.assign(N + 1, -1);

		int cc = 0;
		sat[0] = sat[1] = true;

		for (int i = 1; i <= N; ++i) {
			if (getbit(mask, i) == 0 && color[i] == -1) {
				dfs(i, 0, 0);
				++cc;
			}
		}
		
		for (int i = 1; i <= N; ++i) {
			if (getbit(mask, i) == 1 && color[i] == -1) {
				dfs(i, 0, 1);
				++cc;
			}
		}

		if (sat[0] && sat[1]) res += 1LL << cc;
	}
	return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 30 / 30
• Subtask 5: 0 / 35