oj.uz

Submission #130081

# Submission time Handle Problem Language Result Execution time Memory
130081 2019-07-13T20:54:59 Z TadijaSebez Paths (BOI18_paths) C++11
100 / 100
 796 ms 106744 KB 
#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

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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 8 ms 7416 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 15352 KB Output is correct
2 Correct 136 ms 13356 KB Output is correct
3 Correct 649 ms 105844 KB Output is correct
4 Correct 241 ms 23784 KB Output is correct
5 Correct 176 ms 23664 KB Output is correct
6 Correct 461 ms 75808 KB Output is correct
7 Correct 682 ms 106048 KB Output is correct
8 Correct 647 ms 106744 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 8 ms 7416 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 163 ms 15352 KB Output is correct
12 Correct 136 ms 13356 KB Output is correct
13 Correct 649 ms 105844 KB Output is correct
14 Correct 241 ms 23784 KB Output is correct
15 Correct 176 ms 23664 KB Output is correct
16 Correct 461 ms 75808 KB Output is correct
17 Correct 682 ms 106048 KB Output is correct
18 Correct 647 ms 106744 KB Output is correct
19 Correct 170 ms 15256 KB Output is correct
20 Correct 137 ms 13404 KB Output is correct
21 Correct 603 ms 106096 KB Output is correct
22 Correct 186 ms 23672 KB Output is correct
23 Correct 146 ms 23672 KB Output is correct
24 Correct 486 ms 75808 KB Output is correct
25 Correct 778 ms 105976 KB Output is correct
26 Correct 581 ms 106680 KB Output is correct
27 Correct 202 ms 13304 KB Output is correct
28 Correct 253 ms 16840 KB Output is correct
29 Correct 796 ms 106056 KB Output is correct
30 Correct 650 ms 60268 KB Output is correct
31 Correct 632 ms 60268 KB Output is correct
32 Correct 739 ms 105936 KB Output is correct
33 Correct 8 ms 7416 KB Output is correct
34 Correct 8 ms 7416 KB Output is correct
35 Correct 8 ms 7416 KB Output is correct
36 Correct 8 ms 7416 KB Output is correct
37 Correct 8 ms 7416 KB Output is correct
38 Correct 8 ms 7416 KB Output is correct
39 Correct 8 ms 7388 KB Output is correct
40 Correct 8 ms 7416 KB Output is correct
41 Correct 8 ms 7416 KB Output is correct
42 Correct 8 ms 7416 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 117 ms 9336 KB Output is correct
3 Correct 51 ms 9332 KB Output is correct
4 Correct 173 ms 40228 KB Output is correct
5 Correct 142 ms 40816 KB Output is correct
6 Correct 243 ms 40056 KB Output is correct
7 Correct 71 ms 9336 KB Output is correct
8 Correct 217 ms 40180 KB Output is correct
9 Correct 175 ms 40744 KB Output is correct
10 Correct 222 ms 40736 KB Output is correct
11 Correct 203 ms 24636 KB Output is correct
12 Correct 189 ms 32904 KB Output is correct
13 Correct 259 ms 24648 KB Output is correct
14 Correct 258 ms 40064 KB Output is correct
15 Correct 218 ms 40212 KB Output is correct
16 Correct 8 ms 7416 KB Output is correct
17 Correct 8 ms 7388 KB Output is correct
18 Correct 8 ms 7416 KB Output is correct
19 Correct 8 ms 7392 KB Output is correct
20 Correct 8 ms 7388 KB Output is correct
21 Correct 8 ms 7416 KB Output is correct
22 Correct 8 ms 7416 KB Output is correct
23 Correct 8 ms 7416 KB Output is correct
24 Correct 8 ms 7416 KB Output is correct
25 Correct 8 ms 7416 KB Output is correct