oj.uz

Submission #532

# Submission time Handle Problem Language Result Execution time Memory
532 2013-02-28T11:00:28 Z kriii 지도 색칠하기 (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 5 ms 22448 KB Output is correct
7 Correct 5 ms 22448 KB Output is correct
8 Correct 3 ms 22448 KB Output is correct
9 Correct 1 ms 22448 KB Output is correct
10 Correct 15 ms 22448 KB Output is correct
11 Correct 19 ms 22448 KB Output is correct
12 Correct 7 ms 22448 KB Output is correct
13 Correct 22 ms 22448 KB Output is correct
14 Correct 9 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 18 ms 22448 KB Output is correct
19 Correct 6 ms 22448 KB Output is correct
20 Correct 5 ms 22448 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 22448 KB Output is correct
5 Correct 2 ms 22448 KB Output is correct
6 Correct 83 ms 22448 KB Output is correct
7 Correct 284 ms 22448 KB Output is correct
8 Correct 167 ms 22448 KB Output is correct
9 Correct 505 ms 22448 KB Output is correct
10 Correct 469 ms 22448 KB Output is correct
11 Correct 188 ms 22448 KB Output is correct
12 Correct 179 ms 22448 KB Output is correct
13 Correct 378 ms 22448 KB Output is correct
14 Correct 288 ms 22448 KB Output is correct
15 Correct 83 ms 22448 KB Output is correct
16 Correct 13 ms 22448 KB Output is correct
17 Correct 13 ms 22448 KB Output is correct
18 Correct 161 ms 22448 KB Output is correct
19 Correct 370 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 1 ms 22448 KB Output is correct
3 Correct 4 ms 22448 KB Output is correct
4 Correct 5 ms 22448 KB Output is correct
5 Correct 99 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 -