Submission #17307

#	Time	Username	Problem	Language	Result	Execution time	Memory
17307		gs14004	지도 색칠하기 (GA3_map)	C++14	120 / 120	1114 ms	1084 KiB

map

#include <algorithm>
using namespace std;

bool adj[20][20];
int col[20];

int bits, n;
bool bad;

void dfs(int x, int p){
	if(col[x]){
		bad |= (col[x] != p);
		return;
	}
	col[x] = p;
	for(int i=0; i<n; i++){
		if(adj[x][i] && (bits >> i) % 2 == (bits >> x) % 2){
			dfs(i, 3-p);
		}
	}
}

long long NumberOfMaps (int N, int M, int *A, int *B){
	n = N;
	for(int i=0; i<M; i++){
		adj[A[i]-1][B[i]-1] = 1;
		adj[B[i]-1][A[i]-1] = 1;
	}
	long long sum = 0;
	for(int i=0; i<(1<<(N-1)); i++){
		fill(col, col + N, 0);
		bits = i;
		bad = 0;
		int cnt = 0;
		for(int i=0; i<N; i++){
			if(col[i]) continue;
			dfs(i, 1);
			if(bad) break;
			cnt++;
		}
		if(bad) continue;
		sum += (2 << cnt);
	}
	return sum;
}

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