oj.uz

Submission #426254

# Submission time Handle Problem Language Result Execution time Memory
426254 2021-06-13T15:52:15 Z lovrot Paths (BOI18_paths) C++11
23 / 100
 73 ms 11040 KB 
#include <bits/stdc++.h>

#define X first
#define Y second
#define ll long long

using namespace std;

const int N = 2010;

int n,a,b;
int c[N];
long long int out;
long long int memo[N][N];

vector<int> p[N];

long long int dfs(int x,int y){
	if(memo[x][y] != 0)
		return memo[x][y];

	memo[x][y] = 1;

	for(int i=0;i<p[x].size();i++){ 
		if((1<<c[p[x][i]]) & y)
			continue;

		memo[x][y]+=dfs(p[x][i],y+(1<<c[p[x][i]]));
	}	

	return memo[x][y];
}

int main(){
	ios_base::sync_with_stdio(false);
	int m,k; 

	cin >> n >> m >> k;

	for(int i=0;i<n;i++)
		cin >> c[i];

	for(int i=0;i<m;i++){ 
		cin >> a >> b;
		a--;
		b--;
		p[a].push_back(b);
		p[b].push_back(a);
	}


	for(int i=0;i<n;i++){ 
		out+=dfs(i,0+(1<<c[i]));
	}
	cout<< out-n << "\n";
	return 0;
}

Compilation message

paths.cpp: In function 'long long int dfs(int, int)':
paths.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i=0;i<p[x].size();i++){
      |              ~^~~~~~~~~~~~

Subtask #1
23.0 / 23.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 73 ms 6812 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 44 ms 4356 KB Output is correct
3 Correct 27 ms 4160 KB Output is correct
4 Runtime error 36 ms 11040 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -