Submission #534

# Submission time Handle Problem Language Result Execution time Memory
534 2013-02-28T11:20:16 Z kriii 쉬운 문제 (GA3_easy) C++
Compilation error
0 ms 0 KB
#include <queue>
#include <vector>
using namespace std;

vector<int> U[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];
		}
	}

	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]){
		int x = (1 << N) - 1 - i;
		for (j=x;j;j=(j-1)&x){
			U[i+j].push_back(i);
		}
		U[i].push_back(i);
	}

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

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

	return ret;
}

Compilation message

grader.cpp:26:2: warning: no newline at end of file
easy.cpp: In function 'long long int NumberOfMaps(int, int, int*, int*)':
easy.cpp:69: warning: comparison between signed and unsigned integer expressions
/tmp/ccg7pkv1.o: In function `main':
grader.cpp:(.text+0x87): undefined reference to `CountPair(int, int*)'
collect2: ld returned 1 exit status