답안 #7376 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7376	2014-08-04T15:35:14 Z	gs13068	지도 색칠하기 (GA3_map)	C++	120 / 120	860 ms	1088 KB

int graph[20][20];
int size[20];
int d[20];
bool vis[20];
int q[20];
int qn;

long long NumberOfMaps(int n,int m,int s[],int e[])
{
	long long ans=0,cnt;
	int i,j,k,l;
	for(i=0;i<m;i++)
  {
		graph[s[i]-1][size[s[i]-1]++]=e[i]-1;
		graph[e[i]-1][size[e[i]-1]++]=s[i]-1;
	}
	for(i=0;i<1<<(n-1);i++)
	{
		for(j=0;j<n;j++)vis[j]=false;
		cnt=1;

		for(l=0;l<n;l++)
		{
			if(((1<<l)&i)&&!vis[l])
			{
				qn=0;
				d[l]=0;
				q[qn++]=l;
				vis[l]=true;
				for(j=0;j<qn;j++)
				{
					for(k=0;k<size[q[j]];k++)
					{
						if((1<<graph[q[j]][k])&i)
						{
							if(!vis[graph[q[j]][k]])
							{
								d[graph[q[j]][k]]=1^d[q[j]];
								q[qn++]=graph[q[j]][k];
								vis[graph[q[j]][k]]=true;
							}
							else if(d[graph[q[j]][k]]==d[q[j]])
								break;
						}
					}
					if(k<size[q[j]])break;
				}
				if(j<qn)break;
				cnt<<=1;
			}
		}
		if(l<n)continue;

		for(l=0;l<n;l++)
		{
			if((!((1<<l)&i))&&!vis[l])
			{
				qn=0;
				d[l]=0;
				q[qn++]=l;
				vis[l]=true;
				for(j=0;j<qn;j++)
				{
					for(k=0;k<size[q[j]];k++)
					{
						if(!((1<<graph[q[j]][k])&i))
						{
							if(!vis[graph[q[j]][k]])
							{
								d[graph[q[j]][k]]=1^d[q[j]];
								q[qn++]=graph[q[j]][k];
								vis[graph[q[j]][k]]=true;
							}
							else if(d[graph[q[j]][k]]==d[q[j]])
								break;
						}
					}
					if(k<size[q[j]])break;
				}
				if(j<qn)break;
				cnt<<=1;
			}
		}
		if(l<n)continue;

		ans+=cnt;
	}
	return ans*2;
}

Subtask #1
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	1088 KB	Output is correct
2	Correct	1088 KB	Output is correct
3	Correct	1088 KB	Output is correct
4	Correct	1088 KB	Output is correct
5	Correct	1088 KB	Output is correct
6	Correct	1088 KB	Output is correct
7	Correct	1088 KB	Output is correct
8	Correct	1088 KB	Output is correct
9	Correct	1088 KB	Output is correct
10	Correct	1088 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	메모리	Grader output
1	Correct	1088 KB	Output is correct
2	Correct	1088 KB	Output is correct
3	Correct	1088 KB	Output is correct
4	Correct	1088 KB	Output is correct
5	Correct	1088 KB	Output is correct
6	Correct	1088 KB	Output is correct
7	Correct	1088 KB	Output is correct
8	Correct	1088 KB	Output is correct
9	Correct	1088 KB	Output is correct
10	Correct	1088 KB	Output is correct
11	Correct	1088 KB	Output is correct
12	Correct	1088 KB	Output is correct
13	Correct	1088 KB	Output is correct
14	Correct	1088 KB	Output is correct
15	Correct	1088 KB	Output is correct
16	Correct	1088 KB	Output is correct
17	Correct	1088 KB	Output is correct
18	Correct	1088 KB	Output is correct
19	Correct	1088 KB	Output is correct
20	Correct	1088 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1088 KB	Output is correct
2	Correct	0 ms	1088 KB	Output is correct
3	Correct	0 ms	1088 KB	Output is correct
4	Correct	0 ms	1088 KB	Output is correct
5	Correct	0 ms	1088 KB	Output is correct
6	Correct	4 ms	1088 KB	Output is correct
7	Correct	0 ms	1088 KB	Output is correct
8	Correct	0 ms	1088 KB	Output is correct
9	Correct	0 ms	1088 KB	Output is correct
10	Correct	0 ms	1088 KB	Output is correct
11	Correct	0 ms	1088 KB	Output is correct
12	Correct	0 ms	1088 KB	Output is correct
13	Correct	0 ms	1088 KB	Output is correct
14	Correct	0 ms	1088 KB	Output is correct
15	Correct	0 ms	1088 KB	Output is correct
16	Correct	8 ms	1088 KB	Output is correct
17	Correct	4 ms	1088 KB	Output is correct
18	Correct	0 ms	1088 KB	Output is correct
19	Correct	0 ms	1088 KB	Output is correct
20	Correct	0 ms	1088 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	1088 KB	Output is correct
2	Correct	16 ms	1088 KB	Output is correct
3	Correct	8 ms	1088 KB	Output is correct
4	Correct	8 ms	1088 KB	Output is correct
5	Correct	16 ms	1088 KB	Output is correct
6	Correct	12 ms	1088 KB	Output is correct
7	Correct	28 ms	1088 KB	Output is correct
8	Correct	4 ms	1088 KB	Output is correct
9	Correct	12 ms	1088 KB	Output is correct
10	Correct	16 ms	1088 KB	Output is correct
11	Correct	4 ms	1088 KB	Output is correct
12	Correct	4 ms	1088 KB	Output is correct
13	Correct	8 ms	1088 KB	Output is correct
14	Correct	8 ms	1088 KB	Output is correct
15	Correct	4 ms	1088 KB	Output is correct
16	Correct	80 ms	1088 KB	Output is correct
17	Correct	76 ms	1088 KB	Output is correct
18	Correct	0 ms	1088 KB	Output is correct
19	Correct	8 ms	1088 KB	Output is correct
20	Correct	4 ms	1088 KB	Output is correct

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	64 ms	1088 KB	Output is correct
2	Correct	64 ms	1088 KB	Output is correct
3	Correct	68 ms	1088 KB	Output is correct
4	Correct	68 ms	1088 KB	Output is correct
5	Correct	100 ms	1088 KB	Output is correct
6	Correct	88 ms	1088 KB	Output is correct
7	Correct	92 ms	1088 KB	Output is correct
8	Correct	80 ms	1088 KB	Output is correct
9	Correct	52 ms	1088 KB	Output is correct
10	Correct	92 ms	1088 KB	Output is correct
11	Correct	40 ms	1088 KB	Output is correct
12	Correct	36 ms	1088 KB	Output is correct
13	Correct	48 ms	1088 KB	Output is correct
14	Correct	40 ms	1088 KB	Output is correct
15	Correct	44 ms	1088 KB	Output is correct
16	Correct	364 ms	1088 KB	Output is correct
17	Correct	372 ms	1088 KB	Output is correct
18	Correct	44 ms	1088 KB	Output is correct
19	Correct	40 ms	1088 KB	Output is correct
20	Correct	48 ms	1088 KB	Output is correct
21	Correct	852 ms	1088 KB	Output is correct
22	Correct	860 ms	1088 KB	Output is correct
23	Correct	112 ms	1088 KB	Output is correct
24	Correct	76 ms	1088 KB	Output is correct
25	Correct	80 ms	1088 KB	Output is correct
26	Correct	192 ms	1088 KB	Output is correct
27	Correct	236 ms	1088 KB	Output is correct
28	Correct	224 ms	1088 KB	Output is correct
29	Correct	196 ms	1088 KB	Output is correct
30	Correct	204 ms	1088 KB	Output is correct

답안 #7376

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 25.0 / 25.0

Subtask #4 30.0 / 30.0

Subtask #5 35.0 / 35.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
25.0 / 25.0

Subtask #4
30.0 / 30.0

Subtask #5
35.0 / 35.0