oj.uz

Submission #728481

# Submission time Handle Problem Language Result Execution time Memory
728481 2023-04-22T13:41:31 Z WonderfulWhale Paths (BOI18_paths) C++17
100 / 100
 370 ms 100472 KB 
#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

int ans[300009][1<<5];
vector<int> G[300009];
int tab[300009];

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m, k;
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++) {
		cin >> tab[i];
		tab[i]--;
	}
	for(int i=0;i<m;i++) {
		int a, b;
		cin >> a >> b;
		G[a].pb(b);
		G[b].pb(a);
	}
	for(int i=1;i<=n;i++) {
		ans[i][1<<tab[i]] = 1;
	}
	int res = 0;
	for(int i=1;i<(1<<k);i++) {
		if(__builtin_popcount(i)==1) continue;
		for(int j=1;j<=n;j++) {
			if((i&(1<<tab[j]))==0) continue;
			int rem = i^(1<<tab[j]);
			for(int x:G[j]) {
				ans[j][i] += ans[x][rem];
			}
			res += ans[j][i];
		}
	}
	cout << res << "\n";
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7288 KB Output is correct
2 Correct 4 ms 7384 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7384 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7296 KB Output is correct
7 Correct 4 ms 7316 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 18636 KB Output is correct
2 Correct 70 ms 16944 KB Output is correct
3 Correct 277 ms 99860 KB Output is correct
4 Correct 130 ms 26624 KB Output is correct
5 Correct 101 ms 26572 KB Output is correct
6 Correct 189 ms 72012 KB Output is correct
7 Correct 258 ms 99780 KB Output is correct
8 Correct 292 ms 100428 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7288 KB Output is correct
2 Correct 4 ms 7384 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7384 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7296 KB Output is correct
7 Correct 4 ms 7316 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7384 KB Output is correct
11 Correct 68 ms 18636 KB Output is correct
12 Correct 70 ms 16944 KB Output is correct
13 Correct 277 ms 99860 KB Output is correct
14 Correct 130 ms 26624 KB Output is correct
15 Correct 101 ms 26572 KB Output is correct
16 Correct 189 ms 72012 KB Output is correct
17 Correct 258 ms 99780 KB Output is correct
18 Correct 292 ms 100428 KB Output is correct
19 Correct 73 ms 18672 KB Output is correct
20 Correct 51 ms 16936 KB Output is correct
21 Correct 296 ms 99752 KB Output is correct
22 Correct 115 ms 26576 KB Output is correct
23 Correct 110 ms 26604 KB Output is correct
24 Correct 188 ms 71984 KB Output is correct
25 Correct 273 ms 99788 KB Output is correct
26 Correct 266 ms 100472 KB Output is correct
27 Correct 59 ms 16908 KB Output is correct
28 Correct 90 ms 20896 KB Output is correct
29 Correct 339 ms 99932 KB Output is correct
30 Correct 226 ms 58824 KB Output is correct
31 Correct 237 ms 58932 KB Output is correct
32 Correct 370 ms 99880 KB Output is correct
33 Correct 4 ms 7388 KB Output is correct
34 Correct 4 ms 7380 KB Output is correct
35 Correct 4 ms 7380 KB Output is correct
36 Correct 4 ms 7380 KB Output is correct
37 Correct 4 ms 7380 KB Output is correct
38 Correct 5 ms 7380 KB Output is correct
39 Correct 4 ms 7380 KB Output is correct
40 Correct 6 ms 7380 KB Output is correct
41 Correct 4 ms 7380 KB Output is correct
42 Correct 5 ms 7380 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 22 ms 10324 KB Output is correct
3 Correct 19 ms 10332 KB Output is correct
4 Correct 91 ms 38060 KB Output is correct
5 Correct 56 ms 38464 KB Output is correct
6 Correct 138 ms 37940 KB Output is correct
7 Correct 23 ms 10388 KB Output is correct
8 Correct 101 ms 38288 KB Output is correct
9 Correct 68 ms 38512 KB Output is correct
10 Correct 78 ms 38188 KB Output is correct
11 Correct 80 ms 24036 KB Output is correct
12 Correct 82 ms 31144 KB Output is correct
13 Correct 72 ms 24180 KB Output is correct
14 Correct 121 ms 38060 KB Output is correct
15 Correct 141 ms 38144 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 4 ms 7384 KB Output is correct
19 Correct 4 ms 7392 KB Output is correct
20 Correct 3 ms 7380 KB Output is correct
21 Correct 4 ms 7380 KB Output is correct
22 Correct 6 ms 7380 KB Output is correct
23 Correct 4 ms 7380 KB Output is correct
24 Correct 4 ms 7380 KB Output is correct
25 Correct 4 ms 7380 KB Output is correct