| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 462615 |
2021-08-11T00:12:38 Z |
JovanB |
Paths (BOI18_paths) |
C++17 |
|
518 ms |
97168 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll dp[300005][32];
vector <int> graf[300005];
int col[300005];
int main(){
ios_base::sync_with_stdio(false);
cout.precision(10);
cout<<fixed;
int n, m, k;
cin >> n >> m >> k;
for(int i=1; i<=n; i++){
cin >> col[i];
col[i]--;
dp[i][(1<<col[i])] = 1;
}
for(int i=1; i<=m; i++){
int a, b;
cin >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
}
ll res = -n;
for(int j=0; j<(1<<k); j++){
for(int i=1; i<=n; i++){
if(!((1<<col[i]) & j)){
continue;
}
for(auto c : graf[i]){
dp[i][j] += dp[c][j - (1<<col[i])];
}
res += dp[i][j];
}
}
cout << res << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7392 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7368 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7368 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 7 |
Correct |
7 ms |
7372 KB |
Output is correct |
| 8 |
Correct |
6 ms |
7376 KB |
Output is correct |
| 9 |
Correct |
6 ms |
7244 KB |
Output is correct |
| 10 |
Correct |
6 ms |
7356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
15056 KB |
Output is correct |
| 2 |
Correct |
100 ms |
13356 KB |
Output is correct |
| 3 |
Correct |
431 ms |
96400 KB |
Output is correct |
| 4 |
Correct |
132 ms |
22740 KB |
Output is correct |
| 5 |
Correct |
153 ms |
22724 KB |
Output is correct |
| 6 |
Correct |
271 ms |
69404 KB |
Output is correct |
| 7 |
Correct |
371 ms |
96440 KB |
Output is correct |
| 8 |
Correct |
355 ms |
97168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7392 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7368 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7368 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 7 |
Correct |
7 ms |
7372 KB |
Output is correct |
| 8 |
Correct |
6 ms |
7376 KB |
Output is correct |
| 9 |
Correct |
6 ms |
7244 KB |
Output is correct |
| 10 |
Correct |
6 ms |
7356 KB |
Output is correct |
| 11 |
Correct |
114 ms |
15056 KB |
Output is correct |
| 12 |
Correct |
100 ms |
13356 KB |
Output is correct |
| 13 |
Correct |
431 ms |
96400 KB |
Output is correct |
| 14 |
Correct |
132 ms |
22740 KB |
Output is correct |
| 15 |
Correct |
153 ms |
22724 KB |
Output is correct |
| 16 |
Correct |
271 ms |
69404 KB |
Output is correct |
| 17 |
Correct |
371 ms |
96440 KB |
Output is correct |
| 18 |
Correct |
355 ms |
97168 KB |
Output is correct |
| 19 |
Correct |
90 ms |
15064 KB |
Output is correct |
| 20 |
Correct |
86 ms |
13420 KB |
Output is correct |
| 21 |
Correct |
395 ms |
96516 KB |
Output is correct |
| 22 |
Correct |
132 ms |
22748 KB |
Output is correct |
| 23 |
Correct |
178 ms |
22704 KB |
Output is correct |
| 24 |
Correct |
315 ms |
69360 KB |
Output is correct |
| 25 |
Correct |
409 ms |
96504 KB |
Output is correct |
| 26 |
Correct |
410 ms |
97120 KB |
Output is correct |
| 27 |
Correct |
74 ms |
13356 KB |
Output is correct |
| 28 |
Correct |
140 ms |
16556 KB |
Output is correct |
| 29 |
Correct |
499 ms |
96516 KB |
Output is correct |
| 30 |
Correct |
343 ms |
55264 KB |
Output is correct |
| 31 |
Correct |
411 ms |
55344 KB |
Output is correct |
| 32 |
Correct |
518 ms |
96476 KB |
Output is correct |
| 33 |
Correct |
6 ms |
7372 KB |
Output is correct |
| 34 |
Correct |
6 ms |
7372 KB |
Output is correct |
| 35 |
Correct |
6 ms |
7372 KB |
Output is correct |
| 36 |
Correct |
6 ms |
7372 KB |
Output is correct |
| 37 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 38 |
Correct |
6 ms |
7352 KB |
Output is correct |
| 39 |
Correct |
8 ms |
7372 KB |
Output is correct |
| 40 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 41 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 42 |
Correct |
5 ms |
7288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7308 KB |
Output is correct |
| 2 |
Correct |
38 ms |
9312 KB |
Output is correct |
| 3 |
Correct |
30 ms |
9328 KB |
Output is correct |
| 4 |
Correct |
96 ms |
36936 KB |
Output is correct |
| 5 |
Correct |
82 ms |
37588 KB |
Output is correct |
| 6 |
Correct |
207 ms |
36932 KB |
Output is correct |
| 7 |
Correct |
30 ms |
9464 KB |
Output is correct |
| 8 |
Correct |
132 ms |
36936 KB |
Output is correct |
| 9 |
Correct |
95 ms |
37644 KB |
Output is correct |
| 10 |
Correct |
122 ms |
37696 KB |
Output is correct |
| 11 |
Correct |
102 ms |
23032 KB |
Output is correct |
| 12 |
Correct |
108 ms |
30496 KB |
Output is correct |
| 13 |
Correct |
107 ms |
23244 KB |
Output is correct |
| 14 |
Correct |
194 ms |
36904 KB |
Output is correct |
| 15 |
Correct |
210 ms |
37108 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 17 |
Correct |
6 ms |
7372 KB |
Output is correct |
| 18 |
Correct |
6 ms |
7376 KB |
Output is correct |
| 19 |
Correct |
6 ms |
7372 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 21 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 22 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 23 |
Correct |
6 ms |
7372 KB |
Output is correct |
| 24 |
Correct |
5 ms |
7368 KB |
Output is correct |
| 25 |
Correct |
5 ms |
7372 KB |
Output is correct |
