답안 #63197 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63197	2018-08-01T05:26:11 Z	정원준(#1835)	Paths (BOI18_paths)	C++11	100 / 100	2915 ms	96340 KB

paths

#include <bits/stdc++.h>
#define L long long

using namespace std;

L n,m,kk,ans;
L dp[300030][32];
L col[300030];
vector<L>bit[6];
vector<L>v[300030];
L a[300030],top;

L bits(L x){
	L ret=0;
	while(x)
	{
		ret+=x%2;
		x/=2;
	}
	return ret;
}


int main()
{
	scanf("%lld %lld %lld",&n,&m,&kk);
	L i,bi,binum,j,k;
	for(i=1;i<32;i++)
	{
		bit[bits(i)].push_back(i);
	}
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&col[i]);
		col[i]--;
	}
	for(i=1;i<=m;i++)
	{
		L s,e;
		scanf("%lld %lld",&s,&e);
		v[s].push_back(e);
		v[e].push_back(s);
	}
	for(i=1;i<=n;i++)
	{
		dp[i][(1<<col[i])]=1;
		ans--;
	}
	for(i=1;i<=kk;i++)
	{
		for(binum=0;binum<bit[i].size();binum++)
		{
			bi=bit[i][binum];
			a[++top]=bi;
		}
	}
	for(bi=1;bi<=top;bi++)
	{
		//printf("%lld\n",i);
			//printf("%lld ",bi);
			for(j=1;j<=n;j++)
			{
				ans+=dp[j][bi];
				if(i==kk) continue;
				for(k=0;k<v[j].size();k++)
				{
					if(!(bi&(1<<col[v[j][k]])))
					{
						dp[v[j][k]][bi|(1<<col[v[j][k]])]+=dp[j][bi];
					}
				}
			}
	}
		//puts("");
	/*for(i=0;i<32;i++)
	{
		for(j=1;j<=n;j++)
		{
			printf("%lld ",dp[j][i]);
		}
		puts("");
	}*/
	printf("%lld",ans);
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(binum=0;binum<bit[i].size();binum++)
               ~~~~~^~~~~~~~~~~~~~
paths.cpp:65:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(k=0;k<v[j].size();k++)
             ~^~~~~~~~~~~~
paths.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n,&m,&kk);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&col[i]);
   ~~~~~^~~~~~~~~~~~~~~~
paths.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&s,&e);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	7416 KB	Output is correct
2	Correct	12 ms	7636 KB	Output is correct
3	Correct	9 ms	7636 KB	Output is correct
4	Correct	10 ms	7636 KB	Output is correct
5	Correct	9 ms	7636 KB	Output is correct
6	Correct	9 ms	7636 KB	Output is correct
7	Correct	9 ms	7636 KB	Output is correct
8	Correct	11 ms	7636 KB	Output is correct
9	Correct	10 ms	7636 KB	Output is correct
10	Correct	10 ms	7636 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	335 ms	16008 KB	Output is correct
2	Correct	229 ms	16008 KB	Output is correct
3	Correct	2827 ms	95540 KB	Output is correct
4	Correct	336 ms	95540 KB	Output is correct
5	Correct	235 ms	95540 KB	Output is correct
6	Correct	1600 ms	95540 KB	Output is correct
7	Correct	2778 ms	95700 KB	Output is correct
8	Correct	2877 ms	96340 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	7416 KB	Output is correct
2	Correct	12 ms	7636 KB	Output is correct
3	Correct	9 ms	7636 KB	Output is correct
4	Correct	10 ms	7636 KB	Output is correct
5	Correct	9 ms	7636 KB	Output is correct
6	Correct	9 ms	7636 KB	Output is correct
7	Correct	9 ms	7636 KB	Output is correct
8	Correct	11 ms	7636 KB	Output is correct
9	Correct	10 ms	7636 KB	Output is correct
10	Correct	10 ms	7636 KB	Output is correct
11	Correct	335 ms	16008 KB	Output is correct
12	Correct	229 ms	16008 KB	Output is correct
13	Correct	2827 ms	95540 KB	Output is correct
14	Correct	336 ms	95540 KB	Output is correct
15	Correct	235 ms	95540 KB	Output is correct
16	Correct	1600 ms	95540 KB	Output is correct
17	Correct	2778 ms	95700 KB	Output is correct
18	Correct	2877 ms	96340 KB	Output is correct
19	Correct	268 ms	96340 KB	Output is correct
20	Correct	229 ms	96340 KB	Output is correct
21	Correct	2915 ms	96340 KB	Output is correct
22	Correct	475 ms	96340 KB	Output is correct
23	Correct	321 ms	96340 KB	Output is correct
24	Correct	1299 ms	96340 KB	Output is correct
25	Correct	2510 ms	96340 KB	Output is correct
26	Correct	2839 ms	96340 KB	Output is correct
27	Correct	224 ms	96340 KB	Output is correct
28	Correct	359 ms	96340 KB	Output is correct
29	Correct	2726 ms	96340 KB	Output is correct
30	Correct	1412 ms	96340 KB	Output is correct
31	Correct	1564 ms	96340 KB	Output is correct
32	Correct	2912 ms	96340 KB	Output is correct
33	Correct	11 ms	96340 KB	Output is correct
34	Correct	9 ms	96340 KB	Output is correct
35	Correct	10 ms	96340 KB	Output is correct
36	Correct	11 ms	96340 KB	Output is correct
37	Correct	11 ms	96340 KB	Output is correct
38	Correct	11 ms	96340 KB	Output is correct
39	Correct	11 ms	96340 KB	Output is correct
40	Correct	8 ms	96340 KB	Output is correct
41	Correct	8 ms	96340 KB	Output is correct
42	Correct	7 ms	96340 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	96340 KB	Output is correct
2	Correct	73 ms	96340 KB	Output is correct
3	Correct	89 ms	96340 KB	Output is correct
4	Correct	625 ms	96340 KB	Output is correct
5	Correct	291 ms	96340 KB	Output is correct
6	Correct	451 ms	96340 KB	Output is correct
7	Correct	75 ms	96340 KB	Output is correct
8	Correct	801 ms	96340 KB	Output is correct
9	Correct	317 ms	96340 KB	Output is correct
10	Correct	342 ms	96340 KB	Output is correct
11	Correct	322 ms	96340 KB	Output is correct
12	Correct	328 ms	96340 KB	Output is correct
13	Correct	186 ms	96340 KB	Output is correct
14	Correct	553 ms	96340 KB	Output is correct
15	Correct	460 ms	96340 KB	Output is correct
16	Correct	9 ms	96340 KB	Output is correct
17	Correct	10 ms	96340 KB	Output is correct
18	Correct	8 ms	96340 KB	Output is correct
19	Correct	8 ms	96340 KB	Output is correct
20	Correct	10 ms	96340 KB	Output is correct
21	Correct	8 ms	96340 KB	Output is correct
22	Correct	8 ms	96340 KB	Output is correct
23	Correct	8 ms	96340 KB	Output is correct
24	Correct	8 ms	96340 KB	Output is correct
25	Correct	11 ms	96340 KB	Output is correct

답안 #63197

Compilation message

Subtask #1 23.0 / 23.0

Subtask #2 20.0 / 20.0

Subtask #3 27.0 / 27.0

Subtask #4 30.0 / 30.0

Subtask #1
23.0 / 23.0

Subtask #2
20.0 / 20.0

Subtask #3
27.0 / 27.0

Subtask #4
30.0 / 30.0