| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 927916 |
2024-02-15T14:03:55 Z |
TAhmed33 |
Paths (BOI18_paths) |
C++ |
|
352 ms |
172392 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[300001][1 << 6];
int a[300001], n, m, k;
vector <int> adj[300001];
ll ans (int pos, int mask) {
ll &ret = dp[pos][mask];
if (ret != -1) return ret;
ret = 1;
for (auto j : adj[pos]) {
if (!((mask >> a[j]) & 1)) {
ret += ans(j, mask ^ (1 << a[j]));
}
}
return ret;
}
int main () {
memset(dp, -1, sizeof(dp));
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i]; a[i]--;
}
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
ll sum = 0;
for (int i = 1; i <= n; i++) {
sum += ans(i, 1 << a[i]);
}
sum -= n;
cout << sum << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
158800 KB |
Output is correct |
| 2 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 3 |
Correct |
19 ms |
158808 KB |
Output is correct |
| 4 |
Correct |
21 ms |
158692 KB |
Output is correct |
| 5 |
Correct |
21 ms |
159068 KB |
Output is correct |
| 6 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 7 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 8 |
Correct |
20 ms |
158856 KB |
Output is correct |
| 9 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 10 |
Correct |
22 ms |
158784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
165352 KB |
Output is correct |
| 2 |
Correct |
116 ms |
164704 KB |
Output is correct |
| 3 |
Correct |
300 ms |
171608 KB |
Output is correct |
| 4 |
Correct |
160 ms |
166548 KB |
Output is correct |
| 5 |
Correct |
147 ms |
166484 KB |
Output is correct |
| 6 |
Correct |
241 ms |
169968 KB |
Output is correct |
| 7 |
Correct |
339 ms |
172116 KB |
Output is correct |
| 8 |
Correct |
302 ms |
172376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
158800 KB |
Output is correct |
| 2 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 3 |
Correct |
19 ms |
158808 KB |
Output is correct |
| 4 |
Correct |
21 ms |
158692 KB |
Output is correct |
| 5 |
Correct |
21 ms |
159068 KB |
Output is correct |
| 6 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 7 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 8 |
Correct |
20 ms |
158856 KB |
Output is correct |
| 9 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 10 |
Correct |
22 ms |
158784 KB |
Output is correct |
| 11 |
Correct |
137 ms |
165352 KB |
Output is correct |
| 12 |
Correct |
116 ms |
164704 KB |
Output is correct |
| 13 |
Correct |
300 ms |
171608 KB |
Output is correct |
| 14 |
Correct |
160 ms |
166548 KB |
Output is correct |
| 15 |
Correct |
147 ms |
166484 KB |
Output is correct |
| 16 |
Correct |
241 ms |
169968 KB |
Output is correct |
| 17 |
Correct |
339 ms |
172116 KB |
Output is correct |
| 18 |
Correct |
302 ms |
172376 KB |
Output is correct |
| 19 |
Correct |
136 ms |
165200 KB |
Output is correct |
| 20 |
Correct |
124 ms |
164564 KB |
Output is correct |
| 21 |
Correct |
305 ms |
171600 KB |
Output is correct |
| 22 |
Correct |
162 ms |
166484 KB |
Output is correct |
| 23 |
Correct |
165 ms |
166548 KB |
Output is correct |
| 24 |
Correct |
242 ms |
170028 KB |
Output is correct |
| 25 |
Correct |
298 ms |
171712 KB |
Output is correct |
| 26 |
Correct |
296 ms |
172392 KB |
Output is correct |
| 27 |
Correct |
126 ms |
164692 KB |
Output is correct |
| 28 |
Correct |
154 ms |
165972 KB |
Output is correct |
| 29 |
Correct |
348 ms |
171604 KB |
Output is correct |
| 30 |
Correct |
288 ms |
168760 KB |
Output is correct |
| 31 |
Correct |
303 ms |
168832 KB |
Output is correct |
| 32 |
Correct |
352 ms |
171692 KB |
Output is correct |
| 33 |
Correct |
20 ms |
158800 KB |
Output is correct |
| 34 |
Correct |
22 ms |
158708 KB |
Output is correct |
| 35 |
Correct |
21 ms |
158812 KB |
Output is correct |
| 36 |
Correct |
20 ms |
158804 KB |
Output is correct |
| 37 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 38 |
Correct |
20 ms |
158796 KB |
Output is correct |
| 39 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 40 |
Correct |
19 ms |
158812 KB |
Output is correct |
| 41 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 42 |
Correct |
19 ms |
158812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 2 |
Correct |
62 ms |
160728 KB |
Output is correct |
| 3 |
Correct |
51 ms |
160612 KB |
Output is correct |
| 4 |
Correct |
96 ms |
163032 KB |
Output is correct |
| 5 |
Correct |
87 ms |
163776 KB |
Output is correct |
| 6 |
Correct |
115 ms |
163156 KB |
Output is correct |
| 7 |
Correct |
55 ms |
160592 KB |
Output is correct |
| 8 |
Correct |
104 ms |
162896 KB |
Output is correct |
| 9 |
Correct |
92 ms |
163788 KB |
Output is correct |
| 10 |
Correct |
107 ms |
163840 KB |
Output is correct |
| 11 |
Correct |
111 ms |
161804 KB |
Output is correct |
| 12 |
Correct |
100 ms |
162892 KB |
Output is correct |
| 13 |
Correct |
102 ms |
162000 KB |
Output is correct |
| 14 |
Correct |
112 ms |
162980 KB |
Output is correct |
| 15 |
Correct |
122 ms |
162976 KB |
Output is correct |
| 16 |
Correct |
21 ms |
158860 KB |
Output is correct |
| 17 |
Correct |
20 ms |
158800 KB |
Output is correct |
| 18 |
Correct |
21 ms |
158812 KB |
Output is correct |
| 19 |
Correct |
20 ms |
158776 KB |
Output is correct |
| 20 |
Correct |
20 ms |
158936 KB |
Output is correct |
| 21 |
Correct |
20 ms |
158804 KB |
Output is correct |
| 22 |
Correct |
21 ms |
159056 KB |
Output is correct |
| 23 |
Correct |
19 ms |
158816 KB |
Output is correct |
| 24 |
Correct |
20 ms |
158812 KB |
Output is correct |
| 25 |
Correct |
20 ms |
158812 KB |
Output is correct |
