Submission #941746

#	Time	Username	Problem	Language	Result	Execution time	Memory
941746		dshfjka	Paths (BOI18_paths)	C++14	100 / 100	333 ms	117648 KiB

paths

#include <bits/stdc++.h>
#define LL long long
const LL N=3e5;
using namespace std;
LL n,m,k;
LL dp[N+5][35];
bool visited[N+5][35];
LL arr[N+5];
vector<LL>adj[N+5];
LL f(LL x, LL mask)
{
	if(visited[x][mask])return dp[x][mask];
	visited[x][mask]=1;
	LL &dyn = dp[x][mask];
	dyn=1;
	for(LL a:adj[x])
	{
		if(mask&(1<<arr[a]))continue;
		dyn+=f(a,mask+(1<<arr[a]));
	}
	return dyn;
}
int main()
{
	scanf("%lld %lld %lld",&n,&m,&k);
	for(LL a=1;a<=n;a++)
	{
		scanf("%lld",&arr[a]);
		arr[a]--;
	}
	for(LL a=1;a<=m;a++)
	{
		LL x,y;
		scanf("%lld %lld",&x,&y);
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	LL res=0;
	for(LL a=1;a<=n;a++)
	{
		res+=f(a,1LL<<arr[a]);
	//	printf("%lld : %lld\n",a,res);
	}
	printf("%lld\n",res-n);	
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%lld %lld %lld",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%lld",&arr[a]);
      |   ~~~~~^~~~~~~~~~~~~~~~
paths.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%lld %lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30