oj.uz

Submission #5108

# Submission time Handle Problem Language Result Execution time Memory
5108 2014-02-08T17:53:13 Z cki86201 지도 색칠하기 (GA3_map) C++
0 / 120
 68 ms 1088 KB 
typedef long long ll;
 
int E[22][22], L[22], C[22], N;
 
bool dfs(int bit,int x,int now)
{
	C[x] = now;
	for(int i=0;i<L[x];i++){
		int t = E[x][i];
		if(bit&1<<t){
			if(C[t] == now)return false;
			if(C[t] == -1)return dfs(bit,t,now^1);
		}
	}
	return true;
}
 
int f(int x)
{
	int ret = 1, i;
	for(i=0;i<N;i++)C[i] = -1;
	for(i=0;i<N;i++){
		if((1<<i&x) && C[i]==-1){
			if(!dfs(x,i,0))return 0;
			ret <<= 1;
		}
	}
	return ret;
}
 
ll NumberOfMaps (int N, int M, int *A, int *B){
	::N = N;
	int i;
	for(i=0;i<M;i++){
		--A[i], --B[i];
		E[A[i]][L[A[i]]++] = B[i];
		E[B[i]][L[B[i]]++] = A[i];
	}
	ll ret = 0;
	for(i=0;i<1<<N-1;i++)ret += f(i) * f(((1<<N)-1)^i);
	return ret<<1;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Correct 0 ms 1088 KB Output is correct
4 Incorrect 0 ms 1088 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 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Correct 0 ms 1088 KB Output is correct
4 Incorrect 0 ms 1088 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 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Correct 0 ms 1088 KB Output is correct
4 Incorrect 0 ms 1088 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 1088 KB Output is correct
2 Correct 16 ms 1088 KB Output is correct
3 Correct 8 ms 1088 KB Output is correct
4 Incorrect 8 ms 1088 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 64 ms 1088 KB Output is correct
2 Correct 64 ms 1088 KB Output is correct
3 Correct 68 ms 1088 KB Output is correct
4 Incorrect 68 ms 1088 KB Output isn't correct
5 Halted 0 ms 0 KB -