oj.uz

Submission #529

# Submission time Handle Problem Language Result Execution time Memory
529 2013-02-28T10:15:56 Z kriii 지도 색칠하기 (GA3_map) C++
0 / 120
 8 ms 18324 KB 
bool P[1<<20];
int S[2][1<<20],con[20]; long long mul[1<<20];

long long pos(int v)
{
	int c = -1;
	while (v){
		v /= 2;
		c++;
	}
	return c;
}

long long NumberOfMaps (int N, int M, int *A, int *B)
{
	long long ret = 0;


	int i,j,u,x,s1,s2,t;

	for (i=0;i<M;i++){
		A[i]--; B[i]--;
		con[A[i]] |= 1 << B[i];
		con[B[i]] |= 1 << A[i];
	}

	P[0] = 1; mul[0] = 1;
	for (i=1;i<(1<<N);i++){
		u = i & (-i);
		if (!P[i-u]) continue;
		P[i] = 1;

		x = pos(u);
		s1 = S[0][i-u] & con[x];
		s2 = S[1][i-u] & con[x];

		if (s1 != 0 && s2 != 0) continue;
		if (s1 == 0 && s2 == 0) mul[i] = mul[i-u] * 2;
		else mul[i] = mul[i-u];
		S[0][i] = S[0][i-u];
		S[1][i] = S[1][i-u];
		if (s1 == 0) S[0][i] |= u;
		else if (s2 == 0) S[1][i] |= u;
	}

	for (i=0;i<(1<<N);i++){
		j = (1<<N)-1 -i;
		ret += mul[i] * mul[j];
	}

	return ret;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18324 KB Output is correct
2 Correct 0 ms 18324 KB Output is correct
3 Correct 0 ms 18324 KB Output is correct
4 Correct 0 ms 18324 KB Output is correct
5 Incorrect 0 ms 18324 KB Output isn't correct
6 Halted 0 ms 0 KB -
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18324 KB Output is correct
2 Correct 0 ms 18324 KB Output is correct
3 Correct 0 ms 18324 KB Output is correct
4 Correct 0 ms 18324 KB Output is correct
5 Incorrect 0 ms 18324 KB Output isn't correct
6 Halted 0 ms 0 KB -
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -
11 Halted 0 ms 0 KB -
12 Halted 0 ms 0 KB -
13 Halted 0 ms 0 KB -
14 Halted 0 ms 0 KB -
15 Halted 0 ms 0 KB -
16 Halted 0 ms 0 KB -
17 Halted 0 ms 0 KB -
18 Halted 0 ms 0 KB -
19 Halted 0 ms 0 KB -
20 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18324 KB Output is correct
2 Correct 0 ms 18324 KB Output is correct
3 Correct 0 ms 18324 KB Output is correct
4 Incorrect 0 ms 18324 KB Output isn't correct
5 Halted 0 ms 0 KB -
6 Halted 0 ms 0 KB -
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -
11 Halted 0 ms 0 KB -
12 Halted 0 ms 0 KB -
13 Halted 0 ms 0 KB -
14 Halted 0 ms 0 KB -
15 Halted 0 ms 0 KB -
16 Halted 0 ms 0 KB -
17 Halted 0 ms 0 KB -
18 Halted 0 ms 0 KB -
19 Halted 0 ms 0 KB -
20 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18324 KB Output is correct
2 Correct 1 ms 18324 KB Output is correct
3 Correct 1 ms 18324 KB Output is correct
4 Incorrect 0 ms 18324 KB Output isn't correct
5 Halted 0 ms 0 KB -
6 Halted 0 ms 0 KB -
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -
11 Halted 0 ms 0 KB -
12 Halted 0 ms 0 KB -
13 Halted 0 ms 0 KB -
14 Halted 0 ms 0 KB -
15 Halted 0 ms 0 KB -
16 Halted 0 ms 0 KB -
17 Halted 0 ms 0 KB -
18 Halted 0 ms 0 KB -
19 Halted 0 ms 0 KB -
20 Halted 0 ms 0 KB -

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18324 KB Output is correct
2 Correct 8 ms 18324 KB Output is correct
3 Correct 8 ms 18324 KB Output is correct
4 Incorrect 5 ms 18324 KB Output isn't correct
5 Halted 0 ms 0 KB -
6 Halted 0 ms 0 KB -
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -
11 Halted 0 ms 0 KB -
12 Halted 0 ms 0 KB -
13 Halted 0 ms 0 KB -
14 Halted 0 ms 0 KB -
15 Halted 0 ms 0 KB -
16 Halted 0 ms 0 KB -
17 Halted 0 ms 0 KB -
18 Halted 0 ms 0 KB -
19 Halted 0 ms 0 KB -
20 Halted 0 ms 0 KB -
21 Halted 0 ms 0 KB -
22 Halted 0 ms 0 KB -
23 Halted 0 ms 0 KB -
24 Halted 0 ms 0 KB -
25 Halted 0 ms 0 KB -
26 Halted 0 ms 0 KB -
27 Halted 0 ms 0 KB -
28 Halted 0 ms 0 KB -
29 Halted 0 ms 0 KB -
30 Halted 0 ms 0 KB -