oj.uz

Submission #533

# Submission time Handle Problem Language Result Execution time Memory
533 2013-02-28T11:10:58 Z tncks0121 지도 색칠하기 (GA3_map) C++
85 / 120
 1500 ms 22448 KB 
#include <queue>
using namespace std;

bool P[1<<20];
int S[2][1<<20],con[20],go[1<<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;

	for (i=0;i<M;i++){
		A[i]--; B[i]--;
		con[A[i]] |= 1 << B[i];
		con[B[i]] |= 1 << A[i];
	}
	for (i=1;i<(1<<N);i++){
		if (i == (i & (-i))) go[i] = con[pos(i)];
		else{
			x = i & (-i);
			go[i] = go[x] | go[i-x];
		}
	}

	P[0] = 1; mul[0] = 1;
	queue<int> Q;
	for (i=0;i<N;i++){
		Q.push(1<<i); S[0][1<<i] = 1<<i; mul[1<<i] = 2;
	}
	while (!Q.empty()){
		x = Q.front(); Q.pop();
		int can = go[x] & (~x);
		while (can){
			int now = (can & (-can));
			u = x + (can & (-can));
			can -= can & (-can);
			if ((S[0][x] & go[now]) && (S[1][x] & go[now])) continue;
			if (mul[u] == 0){
				Q.push(u); mul[u] = 2;
				S[0][u] = S[0][x];
				S[1][u] = S[1][x];
				if ((S[1][x] & go[now])) S[0][u] |= now;
				else S[1][u] |= now;
			}
		}
	}

	for (i=1;i<(1<<N);i++) if (mul[i] == 0){
		for (j=(i-1)&i;j>0;j=(j-1)&i){
			if (mul[j] && mul[i-j]){
				if (go[j] & (i-j)) continue;
				if ((j) & go[i-j]) continue;
				mul[i] = mul[j] * mul[i-j];
				P[i] = 1; break;
			}
		}
	}

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

	return ret;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 22448 KB Output is correct
2 Correct 0 ms 22448 KB Output is correct
3 Correct 0 ms 22448 KB Output is correct
4 Correct 0 ms 22448 KB Output is correct
5 Correct 0 ms 22448 KB Output is correct
6 Correct 0 ms 22448 KB Output is correct
7 Correct 0 ms 22448 KB Output is correct
8 Correct 0 ms 22448 KB Output is correct
9 Correct 0 ms 22448 KB Output is correct
10 Correct 0 ms 22448 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 22448 KB Output is correct
2 Correct 0 ms 22448 KB Output is correct
3 Correct 0 ms 22448 KB Output is correct
4 Correct 0 ms 22448 KB Output is correct
5 Correct 0 ms 22448 KB Output is correct
6 Correct 6 ms 22448 KB Output is correct
7 Correct 5 ms 22448 KB Output is correct
8 Correct 4 ms 22448 KB Output is correct
9 Correct 1 ms 22448 KB Output is correct
10 Correct 13 ms 22448 KB Output is correct
11 Correct 18 ms 22448 KB Output is correct
12 Correct 7 ms 22448 KB Output is correct
13 Correct 21 ms 22448 KB Output is correct
14 Correct 8 ms 22448 KB Output is correct
15 Correct 9 ms 22448 KB Output is correct
16 Correct 0 ms 22448 KB Output is correct
17 Correct 0 ms 22448 KB Output is correct
18 Correct 19 ms 22448 KB Output is correct
19 Correct 7 ms 22448 KB Output is correct
20 Correct 4 ms 22448 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 22448 KB Output is correct
2 Correct 0 ms 22448 KB Output is correct
3 Correct 0 ms 22448 KB Output is correct
4 Correct 1 ms 22448 KB Output is correct
5 Correct 1 ms 22448 KB Output is correct
6 Correct 89 ms 22448 KB Output is correct
7 Correct 279 ms 22448 KB Output is correct
8 Correct 167 ms 22448 KB Output is correct
9 Correct 486 ms 22448 KB Output is correct
10 Correct 463 ms 22448 KB Output is correct
11 Correct 184 ms 22448 KB Output is correct
12 Correct 179 ms 22448 KB Output is correct
13 Correct 379 ms 22448 KB Output is correct
14 Correct 285 ms 22448 KB Output is correct
15 Correct 82 ms 22448 KB Output is correct
16 Correct 14 ms 22448 KB Output is correct
17 Correct 14 ms 22448 KB Output is correct
18 Correct 158 ms 22448 KB Output is correct
19 Correct 360 ms 22448 KB Output is correct
20 Correct 124 ms 22448 KB Output is correct

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22448 KB Output is correct
2 Correct 4 ms 22448 KB Output is correct
3 Correct 3 ms 22448 KB Output is correct
4 Correct 4 ms 22448 KB Output is correct
5 Correct 102 ms 22448 KB Output is correct
6 Execution timed out 1500 ms 0 KB Program timed out
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 -