oj.uz

Submission #5105

# Submission time Handle Problem Language Result Execution time Memory
5105 2014-02-05T23:35:15 Z ainta 지도 색칠하기 (GA3_map) C++
0 / 120
 148 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){
	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];
			}
		}
		if (j != C[x])continue;
		if(chk) E2[x][C2[x]++] = chk, E2[chk][C2[chk]++] = x;
		ck[x] = i;
		Do(x + 1);
		ck[x] = 0;
		if (chk) C2[x]--, C2[chk]--;
	}
}
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
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 8 ms 1092 KB Output is correct
2 Correct 20 ms 1092 KB Output is correct
3 Correct 8 ms 1092 KB Output is correct
4 Incorrect 12 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 84 ms 1092 KB Output is correct
2 Correct 88 ms 1092 KB Output is correct
3 Correct 84 ms 1092 KB Output is correct
4 Correct 92 ms 1092 KB Output is correct
5 Incorrect 148 ms 1092 KB Output isn't correct
6 Halted 0 ms 0 KB -