oj.uz

답안 #5110

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5110 2014-02-08T18:09:14 Z cki86201 지도 색칠하기 (GA3_map) C++
0 / 120
 156 ms 1088 KB 
typedef long long ll;
 
int E[22][22], L[22], C[22], N;
 
bool dfs(int bit,int x,int now)
{
  	bool ret = true;
	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)ret |= dfs(bit,t,now^1);
		}
	}
	return ret;
}
 
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 += (ll)f(i) * f(((1<<N)-1)^i);
	return ret<<1;
}

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 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 Correct 0 ms 1088 KB Output is correct
5 Incorrect 0 ms 1088 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 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 Correct 0 ms 1088 KB Output is correct
5 Incorrect 0 ms 1088 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 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 Correct 0 ms 1088 KB Output is correct
5 Correct 0 ms 1088 KB Output is correct
6 Incorrect 0 ms 1088 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# 결과 실행 시간 메모리 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 Correct 8 ms 1088 KB Output is correct
5 Correct 20 ms 1088 KB Output is correct
6 Incorrect 16 ms 1088 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 1088 KB Output is correct
2 Correct 76 ms 1088 KB Output is correct
3 Correct 80 ms 1088 KB Output is correct
4 Correct 80 ms 1088 KB Output is correct
5 Correct 104 ms 1088 KB Output is correct
6 Incorrect 156 ms 1088 KB Output isn't correct
7 Halted 0 ms 0 KB -