Submission #734

#	Time	Username	Problem	Language	Result	Execution time	Memory
734		jyuno426	지도 색칠하기 (GA3_map)	C++98	0 / 120	0 ms	924 KiB

map

#include <algorithm>

int map[30][30];
int chk[30];

inline long long mapping(int num)
{
	if(num <= 0) return 1;
	if(map[num][0] == 0) return mapping(num-1);

	bool color[5];
	register int i;
	long long ans = 0;

	for(i=1;i<=4;i++) color[i] = false;

	for(i=1;i<=map[num][0];i++)
	{
		if(map[num][i] <= num) break;
		color[chk[map[num][i]]] = true;
	}

	for(i=1;i<=4;i++)
	{
		if(!color[i])
		{
			chk[num] = i;
			ans += mapping(num-1);
			chk[num] = 0;
		}
	}

	return ans;
}

bool cmp(int aa, int bb){return aa > bb;}

long long NumberOfMaps (int N, int M, int *A, int *B){

	int i;

	for(i=0;i<M;i++)
	{
		map[A[i]][++map[A[i]][0]] = B[i];
		map[B[i]][++map[B[i]][0]] = A[i];
	}
	long long ans = 1;
	for(i=1;i<=N;i++) std::sort(map[i]+1,map[i]+(map[i][0]+1),cmp);
	for(i=1;i<=N;i++) if(map[i][0] == 0) ans *= 4;
	while(map[N][0] == 0) N--;
	if(N == 0) return ans;

	chk[N] = 1;
	return 4 * ans * mapping(N-1);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35