| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 543684 |
2022-03-31T08:45:40 Z |
tudor |
Paths (BOI18_paths) |
C++17 |
|
820 ms |
97148 KB |
#include <iostream>
#include <vector>
using namespace std;
const int nmax = 3e5;
const int kmax = 5;
long long dp[nmax][1 << kmax];
/// numarul de lanturi care se termina in i si am trecut prin bitii mask
int c[nmax];
vector < int > g[nmax + 1];
int main() {
int n, m, k, a, b;
cin >> n >> m >> k;
for ( int i = 0; i < n; i++ ) {
cin >> c[i];
c[i]--;
dp[i][1 << c[i]] = 1;
}
for ( int i = 0; i < m; i++ ) {
cin >> a >> b;
a--; b--;
g[a].push_back ( b );
g[b].push_back ( a );
}
for ( int mask = 1; mask < ( 1 << k ); mask++ )
for ( int i = 0; i < n; i++ )
for ( int node: g[i] )
if ( ! ( mask & ( 1 << c[node] ) ) )
dp[node][mask | ( 1 << c[node] )] += dp[i][mask];
long long s = 0;
for ( int mask = 1; mask < ( 1 << k ); mask++ )
if ( mask & ( mask - 1 ) )
for ( int i = 0; i < n; i++ )
s = s + dp[i][mask];
cout << s;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7352 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 10 |
Correct |
5 ms |
7252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
187 ms |
14988 KB |
Output is correct |
| 2 |
Correct |
150 ms |
13376 KB |
Output is correct |
| 3 |
Correct |
593 ms |
96608 KB |
Output is correct |
| 4 |
Correct |
205 ms |
22680 KB |
Output is correct |
| 5 |
Correct |
185 ms |
22708 KB |
Output is correct |
| 6 |
Correct |
389 ms |
69472 KB |
Output is correct |
| 7 |
Correct |
534 ms |
96588 KB |
Output is correct |
| 8 |
Correct |
559 ms |
97148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7352 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 10 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 11 |
Correct |
187 ms |
14988 KB |
Output is correct |
| 12 |
Correct |
150 ms |
13376 KB |
Output is correct |
| 13 |
Correct |
593 ms |
96608 KB |
Output is correct |
| 14 |
Correct |
205 ms |
22680 KB |
Output is correct |
| 15 |
Correct |
185 ms |
22708 KB |
Output is correct |
| 16 |
Correct |
389 ms |
69472 KB |
Output is correct |
| 17 |
Correct |
534 ms |
96588 KB |
Output is correct |
| 18 |
Correct |
559 ms |
97148 KB |
Output is correct |
| 19 |
Correct |
174 ms |
15052 KB |
Output is correct |
| 20 |
Correct |
148 ms |
13308 KB |
Output is correct |
| 21 |
Correct |
543 ms |
96596 KB |
Output is correct |
| 22 |
Correct |
226 ms |
22828 KB |
Output is correct |
| 23 |
Correct |
226 ms |
22664 KB |
Output is correct |
| 24 |
Correct |
375 ms |
69424 KB |
Output is correct |
| 25 |
Correct |
533 ms |
96616 KB |
Output is correct |
| 26 |
Correct |
535 ms |
97100 KB |
Output is correct |
| 27 |
Correct |
178 ms |
13364 KB |
Output is correct |
| 28 |
Correct |
222 ms |
16516 KB |
Output is correct |
| 29 |
Correct |
783 ms |
96492 KB |
Output is correct |
| 30 |
Correct |
505 ms |
55404 KB |
Output is correct |
| 31 |
Correct |
517 ms |
55360 KB |
Output is correct |
| 32 |
Correct |
820 ms |
96500 KB |
Output is correct |
| 33 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 34 |
Correct |
4 ms |
7348 KB |
Output is correct |
| 35 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 36 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 37 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 38 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 39 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 40 |
Correct |
4 ms |
7308 KB |
Output is correct |
| 41 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 42 |
Correct |
4 ms |
7252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 2 |
Correct |
86 ms |
9236 KB |
Output is correct |
| 3 |
Correct |
54 ms |
9244 KB |
Output is correct |
| 4 |
Correct |
151 ms |
36916 KB |
Output is correct |
| 5 |
Correct |
115 ms |
37564 KB |
Output is correct |
| 6 |
Correct |
332 ms |
36996 KB |
Output is correct |
| 7 |
Correct |
62 ms |
9420 KB |
Output is correct |
| 8 |
Correct |
211 ms |
36916 KB |
Output is correct |
| 9 |
Correct |
151 ms |
37652 KB |
Output is correct |
| 10 |
Correct |
170 ms |
37748 KB |
Output is correct |
| 11 |
Correct |
179 ms |
23140 KB |
Output is correct |
| 12 |
Correct |
193 ms |
30352 KB |
Output is correct |
| 13 |
Correct |
173 ms |
23180 KB |
Output is correct |
| 14 |
Correct |
328 ms |
37036 KB |
Output is correct |
| 15 |
Correct |
319 ms |
37008 KB |
Output is correct |
| 16 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 17 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 18 |
Correct |
4 ms |
7352 KB |
Output is correct |
| 19 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 20 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 21 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 22 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 23 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 24 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 25 |
Correct |
4 ms |
7252 KB |
Output is correct |
