oj.uz

Submission #5103

# Submission time Handle Problem Language Result Execution time Memory
5103 2014-02-05T23:27:00 Z ainta 지도 색칠하기 (GA3_map) C++
0 / 120
 56 ms 1092 KB 
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1092 KB Output is correct
2 Correct 0 ms 1092 KB Output is correct
3 Correct 0 ms 1092 KB Output is correct
4 Incorrect 0 ms 1092 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1092 KB Output is correct
2 Correct 0 ms 1092 KB Output is correct
3 Correct 0 ms 1092 KB Output is correct
4 Incorrect 0 ms 1092 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1092 KB Output is correct
2 Correct 0 ms 1092 KB Output is correct
3 Correct 0 ms 1092 KB Output is correct
4 Incorrect 0 ms 1092 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1092 KB Output is correct
2 Correct 4 ms 1092 KB Output is correct
3 Correct 0 ms 1092 KB Output is correct
4 Incorrect 4 ms 1092 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1092 KB Output is correct
2 Correct 28 ms 1092 KB Output is correct
3 Correct 24 ms 1092 KB Output is correct
4 Correct 24 ms 1092 KB Output is correct
5 Incorrect 56 ms 1092 KB Output isn't correct
6 Halted 0 ms 0 KB -