oj.uz

Submission #100154

# Submission time Handle Problem Language Result Execution time Memory
100154 2019-03-09T15:56:32 Z tushar_2658 Paths (BOI18_paths) C++14
23 / 100
 576 ms 96632 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 3e5 + 5;
int arr[maxn];
vector<int> edges[maxn];
int n, m, k;
int dp[1 << 6][maxn];

int call(int mask, int node){
	if(dp[mask][node] != -1)return dp[mask][node];
	int ans = 1;
	for(auto i : edges[node]){
		if((mask >> arr[i]) & 1)continue;
		else {
			ans += call(mask ^ (1 << arr[i]), i);
		}
	}return dp[mask][node] = ans;
}

int main(){
	scanf("%d %d %d", &n, &m, &k);
	for(int i=1; i<=n; i++){
		scanf("%d", &arr[i]);
		//--arr[i];
	}
	for(int i=1; i<=m; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		edges[x].emplace_back(y); 
		edges[y].emplace_back(x);
	}
	memset(dp, -1, sizeof dp);
	int ans = 0, mask = 0;
	for(int i=1; i<=n; i++){
		ans += call((mask ^ (1 << arr[i])), i);
	}cout<<ans-n<<endl;
}

Compilation message

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

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 82552 KB Output is correct
2 Correct 71 ms 82552 KB Output is correct
3 Correct 79 ms 82552 KB Output is correct
4 Correct 72 ms 82552 KB Output is correct
5 Correct 77 ms 82488 KB Output is correct
6 Correct 62 ms 82500 KB Output is correct
7 Correct 62 ms 82656 KB Output is correct
8 Correct 61 ms 82452 KB Output is correct
9 Correct 62 ms 82524 KB Output is correct
10 Correct 68 ms 82552 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 89008 KB Output is correct
2 Correct 167 ms 88336 KB Output is correct
3 Correct 576 ms 96632 KB Output is correct
4 Correct 237 ms 90412 KB Output is correct
5 Correct 222 ms 90372 KB Output is correct
6 Incorrect 336 ms 94688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 82552 KB Output is correct
2 Correct 71 ms 82552 KB Output is correct
3 Correct 79 ms 82552 KB Output is correct
4 Correct 72 ms 82552 KB Output is correct
5 Correct 77 ms 82488 KB Output is correct
6 Correct 62 ms 82500 KB Output is correct
7 Correct 62 ms 82656 KB Output is correct
8 Correct 61 ms 82452 KB Output is correct
9 Correct 62 ms 82524 KB Output is correct
10 Correct 68 ms 82552 KB Output is correct
11 Correct 212 ms 89008 KB Output is correct
12 Correct 167 ms 88336 KB Output is correct
13 Correct 576 ms 96632 KB Output is correct
14 Correct 237 ms 90412 KB Output is correct
15 Correct 222 ms 90372 KB Output is correct
16 Incorrect 336 ms 94688 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 82552 KB Output is correct
2 Incorrect 108 ms 84372 KB Output isn't correct
3 Halted 0 ms 0 KB -