Submission #731

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

map

#include <algorithm>

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

inline long long mapping(int num)
{
	if(num <= 0) return 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;
	}
	
	if(map[num][0] == 0) ans += 4 * mapping(num-1);
	else 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];
	}

	for(i=1;i<=N;i++) std::sort(map[i]+1,map[i]+(map[i][0]+1),cmp);

	return mapping(N);
}

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