oj.uz

Submission #93778

# Submission time Handle Problem Language Result Execution time Memory
93778 2019-01-11T08:16:37 Z kjain_1810 Paths (BOI18_paths) C++17
100 / 100
 485 ms 95608 KB 
#include "bits/stdc++.h"
using namespace std;
int k;
vector <int> g[300010];
int col[300010];
long long M[1 << 5][300010];
 
long long dp(int mask, int node) {
	if(M[mask][node] != -1) return M[mask][node];
	long long ans = 1;
	for(auto i : g[node]) {
		if((mask >> col[i]) & 1) {}
		else {
			ans += dp(mask ^ (1 << col[i]), i);
		}
	}
	return M[mask][node] = ans;
}
 
int main(int argc, char const *argv[])
{
	int n, m;
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &col[i]);
		--col[i];
	}
	for(int i = 0; i < m; i++) {
		int p, q;
		scanf("%d %d", &p, &q);
		g[p].push_back(q);
		g[q].push_back(p);
	}
	memset(M, -1, sizeof M);
	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		ans += dp(1 << col[i], i);
	}
	printf("%lld\n", ans - n);
	return 0;
}

Compilation message

paths.cpp: In function 'int main(int, const char**)':
paths.cpp:23: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:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &col[i]);
   ~~~~~^~~~~~~~~~~~~~~
paths.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 82552 KB Output is correct
2 Correct 57 ms 82552 KB Output is correct
3 Correct 58 ms 82556 KB Output is correct
4 Correct 135 ms 82552 KB Output is correct
5 Correct 69 ms 82552 KB Output is correct
6 Correct 58 ms 82552 KB Output is correct
7 Correct 57 ms 82552 KB Output is correct
8 Correct 57 ms 82524 KB Output is correct
9 Correct 57 ms 82556 KB Output is correct
10 Correct 58 ms 82496 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 88952 KB Output is correct
2 Correct 124 ms 88312 KB Output is correct
3 Correct 416 ms 94948 KB Output is correct
4 Correct 188 ms 89976 KB Output is correct
5 Correct 200 ms 89856 KB Output is correct
6 Correct 339 ms 93260 KB Output is correct
7 Correct 458 ms 95088 KB Output is correct
8 Correct 464 ms 95608 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 82552 KB Output is correct
2 Correct 57 ms 82552 KB Output is correct
3 Correct 58 ms 82556 KB Output is correct
4 Correct 135 ms 82552 KB Output is correct
5 Correct 69 ms 82552 KB Output is correct
6 Correct 58 ms 82552 KB Output is correct
7 Correct 57 ms 82552 KB Output is correct
8 Correct 57 ms 82524 KB Output is correct
9 Correct 57 ms 82556 KB Output is correct
10 Correct 58 ms 82496 KB Output is correct
11 Correct 148 ms 88952 KB Output is correct
12 Correct 124 ms 88312 KB Output is correct
13 Correct 416 ms 94948 KB Output is correct
14 Correct 188 ms 89976 KB Output is correct
15 Correct 200 ms 89856 KB Output is correct
16 Correct 339 ms 93260 KB Output is correct
17 Correct 458 ms 95088 KB Output is correct
18 Correct 464 ms 95608 KB Output is correct
19 Correct 165 ms 88952 KB Output is correct
20 Correct 145 ms 88312 KB Output is correct
21 Correct 448 ms 94868 KB Output is correct
22 Correct 200 ms 89992 KB Output is correct
23 Correct 193 ms 89980 KB Output is correct
24 Correct 362 ms 93288 KB Output is correct
25 Correct 421 ms 94900 KB Output is correct
26 Correct 441 ms 95608 KB Output is correct
27 Correct 152 ms 88440 KB Output is correct
28 Correct 173 ms 89848 KB Output is correct
29 Correct 485 ms 94860 KB Output is correct
30 Correct 330 ms 91884 KB Output is correct
31 Correct 300 ms 92144 KB Output is correct
32 Correct 388 ms 94840 KB Output is correct
33 Correct 67 ms 82524 KB Output is correct
34 Correct 67 ms 82552 KB Output is correct
35 Correct 67 ms 82516 KB Output is correct
36 Correct 68 ms 82524 KB Output is correct
37 Correct 67 ms 82552 KB Output is correct
38 Correct 67 ms 82556 KB Output is correct
39 Correct 66 ms 82552 KB Output is correct
40 Correct 65 ms 82552 KB Output is correct
41 Correct 68 ms 82552 KB Output is correct
42 Correct 66 ms 82628 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 82552 KB Output is correct
2 Correct 102 ms 84280 KB Output is correct
3 Correct 90 ms 84216 KB Output is correct
4 Correct 135 ms 87032 KB Output is correct
5 Correct 136 ms 87764 KB Output is correct
6 Correct 194 ms 87120 KB Output is correct
7 Correct 96 ms 84344 KB Output is correct
8 Correct 161 ms 87036 KB Output is correct
9 Correct 129 ms 87896 KB Output is correct
10 Correct 142 ms 87664 KB Output is correct
11 Correct 148 ms 85692 KB Output is correct
12 Correct 134 ms 86896 KB Output is correct
13 Correct 136 ms 85740 KB Output is correct
14 Correct 193 ms 87032 KB Output is correct
15 Correct 150 ms 87168 KB Output is correct
16 Correct 66 ms 82552 KB Output is correct
17 Correct 57 ms 82552 KB Output is correct
18 Correct 64 ms 82568 KB Output is correct
19 Correct 67 ms 82564 KB Output is correct
20 Correct 68 ms 82552 KB Output is correct
21 Correct 57 ms 82552 KB Output is correct
22 Correct 67 ms 82528 KB Output is correct
23 Correct 58 ms 82552 KB Output is correct
24 Correct 57 ms 82552 KB Output is correct
25 Correct 59 ms 82552 KB Output is correct