제출 #1207447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207447		Trn115	지도 색칠하기 (GA3_map)	C++20	120 / 120	1201 ms	420 KiB

map

#include <bits/stdc++.h>

using namespace std;

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

long long NumberOfMaps (int N, int M, int *A, int *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;
	function<void(int, int, int)> dfs = [&](int v, int c, int type) {
		color[v] = c;
		for (int u : g[v]) {
			if (!sat) break;
			if (getbit(mask, u) != type) continue;
			if (color[u] == -1) {
				dfs(u, c ^ 1, type);
			} else if (color[u] == c) {
				sat = false;
			}
		}
	};

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

		int cc = 0;
		sat = true;

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

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