Submission #5103

#	Time	Username	Problem	Language	Result	Execution time	Memory
5103		ainta	지도 색칠하기 (GA3_map)	C++98	0 / 120	56 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 Do(int x, int A, int B){
	if (x == n + 1){
		ret += (long long)A*B;
		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 = 1;
			}
		}
		if (j != C[x])continue;
		for (j = 0; j != C[x]; j++){
			if (ck[E[x][j]] == i){
				E2[x][C2[x]++] = E[x][j];
				E2[E[x][j]][C2[E[x][j]]++] = x;
			}
		}
		if (!chk){
			if (i)B *= 2; else A *= 2;
		}
		ck[x] = i;
		Do(x + 1, A, B);
		ck[x] = 0;
		if (!chk){
			if (i)B /= 2; else A /= 2;
		}
		for (j = 0; j != C[x]; j++){
			if (ck[E[x][j]] == i){
				C2[x]--, C2[E[x][j]]--;
			}
		}
	}
}
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, 1, 1);
	return ret;
}

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