Submission #63191

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
63191	2018-08-01T05:15:25 Z	정원준(#1835)	Paths (BOI18_paths)	C++11	0 / 100	170 ms	15864 KB

paths

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

using namespace std;

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

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


int main()
{
	scanf("%lld %lld %lld",&n,&m,&k);
	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<=k;i++)
	{
		//printf("%lld\n",i);
		for(binum=0;binum<bit[i].size();binum++)
		{
			bi=bit[i][binum];
			//printf("%lld ",bi);
			for(j=1;j<=n;j++)
			{
				ans+=dp[j][bi];
				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:58:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(k=0;k<v[j].size();k++)
             ~^~~~~~~~~~~~
paths.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&col[i]);
   ~~~~~^~~~~~~~~~~~~~~~
paths.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&s,&e);
   ~~~~~^~~~~~~~~~~~~~~~~~~
paths.cpp:48:11: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for(i=1;i<=k;i++)
          ~^~~

Subtask #1

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	10 ms	7416 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	170 ms	15864 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	10 ms	7416 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	10 ms	15864 KB	Output isn't correct
2	Halted	0 ms	0 KB	-