| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 864452 |
2023-10-23T02:41:35 Z |
maks007 |
Paths (BOI18_paths) |
C++14 |
|
523 ms |
73820 KB |
#include "bits/stdc++.h"
using namespace std;
#define int long long
vector <int> color;
vector <vector <int>> g, dp;
signed main () {
int n, m, k;
cin >> n >> m >> k;
color.resize(n);
g.resize(n);
dp.resize(n, vector <int> (1 << k, 0));
for(int i = 0; i < n; i ++) {
cin >> color[i];
color[i] --;
}
for(int i = 0, u, v; i < m; i ++) {
cin >> u >> v;
u --, v --;
g[u].push_back(v);
g[v].push_back(u);
if(color[u] == color[v]) continue;
dp[v][(1 << color[u]) ^ (1 << color[v])] += 1;
dp[u][(1 << color[u]) ^ (1 << color[v])] += 1;
}
for(int mask = 0; mask < (1 << k); mask ++) {
for(int i = 0; i < n; i ++) {
if(dp[i][mask] == 0 || (!(mask & (1 << color[i])))) continue;
for(auto j : g[i]) {
if(mask & (1 << color[j])) continue;
dp[j][mask ^ (1 << color[j])] += dp[i][mask];
}
}
}
int ans = 0;
for(int mask = 0; mask < (1 << k); mask ++) {
for(int i = 0; i < n; i ++) {
ans += dp[i][mask];
}
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
436 KB |
Output is correct |
| 3 |
Correct |
0 ms |
436 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
356 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
10536 KB |
Output is correct |
| 2 |
Correct |
96 ms |
9672 KB |
Output is correct |
| 3 |
Correct |
388 ms |
54572 KB |
Output is correct |
| 4 |
Correct |
153 ms |
14452 KB |
Output is correct |
| 5 |
Correct |
135 ms |
14160 KB |
Output is correct |
| 6 |
Correct |
302 ms |
39232 KB |
Output is correct |
| 7 |
Correct |
402 ms |
54708 KB |
Output is correct |
| 8 |
Correct |
378 ms |
55120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
436 KB |
Output is correct |
| 3 |
Correct |
0 ms |
436 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
356 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
124 ms |
10536 KB |
Output is correct |
| 12 |
Correct |
96 ms |
9672 KB |
Output is correct |
| 13 |
Correct |
388 ms |
54572 KB |
Output is correct |
| 14 |
Correct |
153 ms |
14452 KB |
Output is correct |
| 15 |
Correct |
135 ms |
14160 KB |
Output is correct |
| 16 |
Correct |
302 ms |
39232 KB |
Output is correct |
| 17 |
Correct |
402 ms |
54708 KB |
Output is correct |
| 18 |
Correct |
378 ms |
55120 KB |
Output is correct |
| 19 |
Correct |
119 ms |
10328 KB |
Output is correct |
| 20 |
Correct |
97 ms |
9680 KB |
Output is correct |
| 21 |
Correct |
391 ms |
54720 KB |
Output is correct |
| 22 |
Correct |
144 ms |
14688 KB |
Output is correct |
| 23 |
Correct |
137 ms |
14168 KB |
Output is correct |
| 24 |
Correct |
300 ms |
39352 KB |
Output is correct |
| 25 |
Correct |
381 ms |
54608 KB |
Output is correct |
| 26 |
Correct |
387 ms |
55364 KB |
Output is correct |
| 27 |
Correct |
106 ms |
9552 KB |
Output is correct |
| 28 |
Correct |
142 ms |
13036 KB |
Output is correct |
| 29 |
Correct |
497 ms |
73820 KB |
Output is correct |
| 30 |
Correct |
343 ms |
41792 KB |
Output is correct |
| 31 |
Correct |
355 ms |
41928 KB |
Output is correct |
| 32 |
Correct |
523 ms |
73520 KB |
Output is correct |
| 33 |
Correct |
0 ms |
348 KB |
Output is correct |
| 34 |
Correct |
1 ms |
348 KB |
Output is correct |
| 35 |
Correct |
0 ms |
348 KB |
Output is correct |
| 36 |
Correct |
0 ms |
604 KB |
Output is correct |
| 37 |
Correct |
0 ms |
348 KB |
Output is correct |
| 38 |
Correct |
0 ms |
348 KB |
Output is correct |
| 39 |
Correct |
0 ms |
604 KB |
Output is correct |
| 40 |
Correct |
0 ms |
348 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 |
43 ms |
3384 KB |
Output is correct |
| 3 |
Correct |
32 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
103 ms |
18392 KB |
Output is correct |
| 5 |
Correct |
85 ms |
18964 KB |
Output is correct |
| 6 |
Correct |
161 ms |
37336 KB |
Output is correct |
| 7 |
Correct |
35 ms |
3268 KB |
Output is correct |
| 8 |
Correct |
134 ms |
24920 KB |
Output is correct |
| 9 |
Correct |
107 ms |
25176 KB |
Output is correct |
| 10 |
Correct |
119 ms |
25296 KB |
Output is correct |
| 11 |
Correct |
96 ms |
20024 KB |
Output is correct |
| 12 |
Correct |
119 ms |
28936 KB |
Output is correct |
| 13 |
Correct |
101 ms |
20552 KB |
Output is correct |
| 14 |
Correct |
160 ms |
37380 KB |
Output is correct |
| 15 |
Correct |
151 ms |
37284 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
344 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
0 ms |
344 KB |
Output is correct |
| 21 |
Correct |
0 ms |
344 KB |
Output is correct |
| 22 |
Correct |
0 ms |
348 KB |
Output is correct |
| 23 |
Correct |
0 ms |
348 KB |
Output is correct |
| 24 |
Correct |
0 ms |
348 KB |
Output is correct |
| 25 |
Correct |
0 ms |
348 KB |
Output is correct |
