Submission #5106

#	Time	Username	Problem	Language	Result	Execution time	Memory
5106		ainta	지도 색칠하기 (GA3_map)	C++98	120 / 120	708 ms	1092 KiB

map

int n, C[21], E[21][21], E2[21][21], C2[21], D[21], ck[21];
long long ret;
void DFS(int x, int d){
	D[x] = d;
	int i;
	for (i = 0; i != C2[x]; i++){
		if (!D[E2[x][i]])DFS(E2[x][i], d + 1);
	}
}
void Clear(int x){
	int i;
	for (i = 0; i < C2[x]; i++){
		C2[E2[x][i]]--;
	}
	C2[x] = 0;
}
void Do(int x){
	if (x == n + 1){
		int i, t = 1;
		for (i = 1; i != x; i++)D[i] = 0;
		for (i = 1; i != x; i++){
			if (!D[i])DFS(i, 1), t *= 2;
		}
		ret = ret + t;
		return;
	}
	int i, j, chk;
	for (i = 1; i <= 2; i++){
		chk = 0;
		for (j = 1; j != x; j++)D[j] = 0;
		for (j = 0; j != C[x]; j++){
			if (ck[E[x][j]] == i){
				if (D[E[x][j]]){
					if (D[E[x][j]] % 2 == 0)break;
				}
				else{
					DFS(E[x][j], 1);
					chk = E[x][j];
					E2[x][C2[x]++] = chk, E2[chk][C2[chk]++] = x;
				}
			}
		}
		if (j != C[x]){
			Clear(x);
			continue;
		}
		ck[x] = i;
		Do(x + 1);
		ck[x] = 0;
		Clear(x);
	}
}
long long NumberOfMaps(int N, int M, int *A, int *B){
	int i;
	for (i = 0; i < M; i++){
		E[A[i]][C[A[i]]++] = B[i];
		E[B[i]][C[B[i]]++] = A[i];
	}
	n = N;
	Do(1);
	return ret;
}

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