Submission #130081

#	Time	Username	Problem	Language	Result	Execution time	Memory
130081		TadijaSebez	Paths (BOI18_paths)	C++11	100 / 100	796 ms	106744 KiB

paths

#include <stdio.h>
#include <vector>
using namespace std;
#define ll long long
const int N=300050;
int col[N];
vector<int> E[N];
ll dp[N][2][2][2][2][2],sol;
bool vis[N][2][2][2][2][2];
ll DFS(int u, vector<int> was)
{
	if(vis[u][was[0]][was[1]][was[2]][was[3]][was[4]])
		return dp[u][was[0]][was[1]][was[2]][was[3]][was[4]];
	ll ret=1;
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(was[col[v]]) continue;
		was[col[v]]=1;
		ret+=DFS(v,was);
		was[col[v]]=0;
	}
	dp[u][was[0]][was[1]][was[2]][was[3]][was[4]]=ret;
	vis[u][was[0]][was[1]][was[2]][was[3]][was[4]]=1;
	return ret;
}
int main()
{
	int n,m,k,i,u,v;
	scanf("%i %i %i",&n,&m,&k);
	for(i=1;i<=n;i++) scanf("%i",&col[i]),col[i]--;
	while(m--) scanf("%i %i",&u,&v),E[u].push_back(v),E[v].push_back(u);
	vector<int> was;
	for(i=1;i<=5;i++) was.push_back(0);
	for(i=1;i<=n;i++)
	{
		was[col[i]]=1;
		sol+=DFS(i,was);
		was[col[i]]=0;
	}
	printf("%lld\n",sol-n);
	return 0;
}

Compilation message (stderr)

paths.cpp: In function 'long long int DFS(int, std::vector<int>)':
paths.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++)
              ~^~~~~~~~~~~~
paths.cpp: In function 'int main()':
paths.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
paths.cpp:31:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=n;i++) scanf("%i",&col[i]),col[i]--;
                    ~~~~~~~~~~~~~~~~~~~^~~~~~~~~
paths.cpp:32:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  while(m--) scanf("%i %i",&u,&v),E[u].push_back(v),E[v].push_back(u);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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