Submission #716439

# Submission time Handle Problem Language Result Execution time Memory
716439 2023-03-30T06:05:24 Z Iliya Paths (BOI18_paths) C++17
100 / 100
585 ms 95940 KB
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
vector<int> Adj[N];
int n, m, k, ans, C[N], dp[N][1 << 5];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> C[i]; C[i]--;
		dp[i][(1 << C[i])] = 1;
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		Adj[u].push_back(v);
		Adj[v].push_back(u);
	}
	for (int mask = 1; mask < (1 << 5); mask++) {
		if (__builtin_popcount(mask) != 1) {
			for (int i = 1; i <= n; i++) {
				if (mask & (1 << C[i])) {
					for (int u : Adj[i]) {
						dp[i][mask] += dp[u][mask ^ (1 << C[i])];
					}
					ans += dp[i][mask];
				}
			}
		}
	}
	cout << ans << '\n';
}
# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7360 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 6 ms 7380 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7380 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 77 ms 15864 KB Output is correct
2 Correct 56 ms 14668 KB Output is correct
3 Correct 483 ms 95380 KB Output is correct
4 Correct 157 ms 23256 KB Output is correct
5 Correct 219 ms 23292 KB Output is correct
6 Correct 354 ms 67844 KB Output is correct
7 Correct 464 ms 95316 KB Output is correct
8 Correct 498 ms 95940 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7360 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 6 ms 7380 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7380 KB Output is correct
11 Correct 77 ms 15864 KB Output is correct
12 Correct 56 ms 14668 KB Output is correct
13 Correct 483 ms 95380 KB Output is correct
14 Correct 157 ms 23256 KB Output is correct
15 Correct 219 ms 23292 KB Output is correct
16 Correct 354 ms 67844 KB Output is correct
17 Correct 464 ms 95316 KB Output is correct
18 Correct 498 ms 95940 KB Output is correct
19 Correct 82 ms 15856 KB Output is correct
20 Correct 59 ms 14652 KB Output is correct
21 Correct 477 ms 95368 KB Output is correct
22 Correct 175 ms 23160 KB Output is correct
23 Correct 168 ms 23256 KB Output is correct
24 Correct 340 ms 67856 KB Output is correct
25 Correct 459 ms 95284 KB Output is correct
26 Correct 495 ms 95920 KB Output is correct
27 Correct 52 ms 14668 KB Output is correct
28 Correct 114 ms 18012 KB Output is correct
29 Correct 558 ms 95376 KB Output is correct
30 Correct 348 ms 54848 KB Output is correct
31 Correct 345 ms 55000 KB Output is correct
32 Correct 585 ms 95400 KB Output is correct
33 Correct 4 ms 7380 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 4 ms 7304 KB Output is correct
39 Correct 4 ms 7380 KB Output is correct
40 Correct 4 ms 7380 KB Output is correct
41 Correct 4 ms 7380 KB Output is correct
42 Correct 4 ms 7380 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 26 ms 9572 KB Output is correct
3 Correct 22 ms 9684 KB Output is correct
4 Correct 145 ms 36716 KB Output is correct
5 Correct 90 ms 37068 KB Output is correct
6 Correct 158 ms 36724 KB Output is correct
7 Correct 26 ms 9708 KB Output is correct
8 Correct 133 ms 36696 KB Output is correct
9 Correct 89 ms 37056 KB Output is correct
10 Correct 108 ms 37320 KB Output is correct
11 Correct 98 ms 22848 KB Output is correct
12 Correct 95 ms 29864 KB Output is correct
13 Correct 84 ms 23240 KB Output is correct
14 Correct 135 ms 36724 KB Output is correct
15 Correct 143 ms 36804 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 5 ms 7400 KB Output is correct
19 Correct 3 ms 7380 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct
21 Correct 5 ms 7380 KB Output is correct
22 Correct 4 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 5 ms 7252 KB Output is correct