| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1051263 |
2024-08-10T02:30:31 Z |
starr |
Paths (BOI18_paths) |
C++17 |
|
634 ms |
764756 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n, m, k;
cin >> n >> m >> k;
vector<int> col(n);
for(int i = 0; i < n; i++) cin >> col[i], col[i]--;
vector<int> adj[n + 5];
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
a--, b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
int dp[k + 5][n + 5][35];
memset(dp, 0, sizeof dp);
for(int i = 0; i < n; i++) dp[0][i][(1 << col[i])] = 1;
for(int i = 1; i < k; i++){
for(int j = 0; j < n; j++){
for(int x : adj[j]){
for(int mask = 0; mask < (1 << k); mask++){
if(!(mask & (1 << col[j]))){
dp[i][j][mask | (1 << col[j])] += dp[i - 1][x][mask];
}
}
}
}
}
// cout << (1 << k) << endl;
int ans = 0;
for(int i = 1; i < k; i++){
for(int j = 0; j < n; j++){
for(int mask = 0; mask < (1 << k); mask++){
ans += dp[i][j][mask];
}
}
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
604 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
18516 KB |
Output is correct |
| 2 |
Correct |
75 ms |
9264 KB |
Output is correct |
| 3 |
Correct |
490 ms |
677856 KB |
Output is correct |
| 4 |
Correct |
126 ms |
67004 KB |
Output is correct |
| 5 |
Correct |
120 ms |
58612 KB |
Output is correct |
| 6 |
Correct |
364 ms |
453824 KB |
Output is correct |
| 7 |
Correct |
566 ms |
682264 KB |
Output is correct |
| 8 |
Correct |
501 ms |
682864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
604 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
92 ms |
18516 KB |
Output is correct |
| 12 |
Correct |
75 ms |
9264 KB |
Output is correct |
| 13 |
Correct |
490 ms |
677856 KB |
Output is correct |
| 14 |
Correct |
126 ms |
67004 KB |
Output is correct |
| 15 |
Correct |
120 ms |
58612 KB |
Output is correct |
| 16 |
Correct |
364 ms |
453824 KB |
Output is correct |
| 17 |
Correct |
566 ms |
682264 KB |
Output is correct |
| 18 |
Correct |
501 ms |
682864 KB |
Output is correct |
| 19 |
Correct |
89 ms |
21328 KB |
Output is correct |
| 20 |
Correct |
70 ms |
11348 KB |
Output is correct |
| 21 |
Correct |
558 ms |
682316 KB |
Output is correct |
| 22 |
Correct |
126 ms |
70224 KB |
Output is correct |
| 23 |
Correct |
117 ms |
62000 KB |
Output is correct |
| 24 |
Correct |
376 ms |
458256 KB |
Output is correct |
| 25 |
Correct |
499 ms |
682612 KB |
Output is correct |
| 26 |
Correct |
498 ms |
682828 KB |
Output is correct |
| 27 |
Correct |
81 ms |
11604 KB |
Output is correct |
| 28 |
Correct |
114 ms |
31828 KB |
Output is correct |
| 29 |
Correct |
623 ms |
764524 KB |
Output is correct |
| 30 |
Correct |
402 ms |
387548 KB |
Output is correct |
| 31 |
Correct |
403 ms |
387784 KB |
Output is correct |
| 32 |
Correct |
634 ms |
764756 KB |
Output is correct |
| 33 |
Correct |
0 ms |
348 KB |
Output is correct |
| 34 |
Correct |
0 ms |
604 KB |
Output is correct |
| 35 |
Correct |
1 ms |
348 KB |
Output is correct |
| 36 |
Correct |
0 ms |
348 KB |
Output is correct |
| 37 |
Correct |
0 ms |
348 KB |
Output is correct |
| 38 |
Correct |
0 ms |
632 KB |
Output is correct |
| 39 |
Correct |
0 ms |
604 KB |
Output is correct |
| 40 |
Correct |
0 ms |
604 KB |
Output is correct |
| 41 |
Correct |
0 ms |
348 KB |
Output is correct |
| 42 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
37 ms |
3920 KB |
Output is correct |
| 3 |
Correct |
24 ms |
4292 KB |
Output is correct |
| 4 |
Correct |
159 ms |
227388 KB |
Output is correct |
| 5 |
Correct |
154 ms |
227784 KB |
Output is correct |
| 6 |
Correct |
255 ms |
282192 KB |
Output is correct |
| 7 |
Correct |
28 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
192 ms |
254884 KB |
Output is correct |
| 9 |
Correct |
179 ms |
255352 KB |
Output is correct |
| 10 |
Correct |
188 ms |
254916 KB |
Output is correct |
| 11 |
Correct |
136 ms |
142732 KB |
Output is correct |
| 12 |
Correct |
174 ms |
212544 KB |
Output is correct |
| 13 |
Correct |
133 ms |
142656 KB |
Output is correct |
| 14 |
Correct |
296 ms |
282400 KB |
Output is correct |
| 15 |
Correct |
254 ms |
282456 KB |
Output is correct |
| 16 |
Correct |
0 ms |
344 KB |
Output is correct |
| 17 |
Correct |
1 ms |
600 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
0 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
604 KB |
Output is correct |
| 22 |
Correct |
0 ms |
604 KB |
Output is correct |
| 23 |
Correct |
0 ms |
600 KB |
Output is correct |
| 24 |
Correct |
0 ms |
348 KB |
Output is correct |
| 25 |
Correct |
0 ms |
348 KB |
Output is correct |
