| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 760198 |
2023-06-17T09:36:40 Z |
MetalPower |
Paths (BOI18_paths) |
C++14 |
|
457 ms |
99532 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MX = 3e5 + 10;
const int MK = 33;
int N, M, K, col[MX];
vector<int> adj[MX];
ll dp[MX][MK];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M >> K;
for(int i = 1; i <= N; i++){
cin >> col[i]; col[i]--;
}
for(int i = 1; i <= M; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1; i <= N; i++) dp[i][1 << col[i]] = 1;
int mx = 1 << K;
for(int mask = 1; mask < mx; mask++){
for(int i = 1; i <= N; i++){
for(int nx : adj[i]){
if((mask >> col[nx] & 1) == 0) dp[nx][mask | 1 << col[nx]] += dp[i][mask];
}
}
}
ll ans = 0;
for(int i = 1; i <= N; i++){
for(int mask = 0; mask < mx; mask++) ans += dp[i][mask];
}
cout << ans - N << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
3 ms |
7388 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7384 KB |
Output is correct |
| 8 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 9 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 10 |
Correct |
3 ms |
7380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
15052 KB |
Output is correct |
| 2 |
Correct |
57 ms |
13408 KB |
Output is correct |
| 3 |
Correct |
287 ms |
98876 KB |
Output is correct |
| 4 |
Correct |
74 ms |
22980 KB |
Output is correct |
| 5 |
Correct |
93 ms |
23024 KB |
Output is correct |
| 6 |
Correct |
196 ms |
70932 KB |
Output is correct |
| 7 |
Correct |
274 ms |
98788 KB |
Output is correct |
| 8 |
Correct |
289 ms |
99532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
3 ms |
7388 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7384 KB |
Output is correct |
| 8 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 9 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 10 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 11 |
Correct |
76 ms |
15052 KB |
Output is correct |
| 12 |
Correct |
57 ms |
13408 KB |
Output is correct |
| 13 |
Correct |
287 ms |
98876 KB |
Output is correct |
| 14 |
Correct |
74 ms |
22980 KB |
Output is correct |
| 15 |
Correct |
93 ms |
23024 KB |
Output is correct |
| 16 |
Correct |
196 ms |
70932 KB |
Output is correct |
| 17 |
Correct |
274 ms |
98788 KB |
Output is correct |
| 18 |
Correct |
289 ms |
99532 KB |
Output is correct |
| 19 |
Correct |
94 ms |
15156 KB |
Output is correct |
| 20 |
Correct |
53 ms |
13444 KB |
Output is correct |
| 21 |
Correct |
272 ms |
98808 KB |
Output is correct |
| 22 |
Correct |
85 ms |
23024 KB |
Output is correct |
| 23 |
Correct |
70 ms |
22940 KB |
Output is correct |
| 24 |
Correct |
197 ms |
70920 KB |
Output is correct |
| 25 |
Correct |
280 ms |
98872 KB |
Output is correct |
| 26 |
Correct |
291 ms |
99532 KB |
Output is correct |
| 27 |
Correct |
75 ms |
13404 KB |
Output is correct |
| 28 |
Correct |
99 ms |
16616 KB |
Output is correct |
| 29 |
Correct |
457 ms |
98868 KB |
Output is correct |
| 30 |
Correct |
298 ms |
56556 KB |
Output is correct |
| 31 |
Correct |
285 ms |
56528 KB |
Output is correct |
| 32 |
Correct |
403 ms |
98848 KB |
Output is correct |
| 33 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 34 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 35 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 36 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 37 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 38 |
Correct |
4 ms |
7384 KB |
Output is correct |
| 39 |
Correct |
4 ms |
7388 KB |
Output is correct |
| 40 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 41 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 42 |
Correct |
3 ms |
7384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7388 KB |
Output is correct |
| 2 |
Correct |
41 ms |
9312 KB |
Output is correct |
| 3 |
Correct |
19 ms |
9300 KB |
Output is correct |
| 4 |
Correct |
70 ms |
37648 KB |
Output is correct |
| 5 |
Correct |
51 ms |
38360 KB |
Output is correct |
| 6 |
Correct |
148 ms |
37728 KB |
Output is correct |
| 7 |
Correct |
26 ms |
9300 KB |
Output is correct |
| 8 |
Correct |
104 ms |
37708 KB |
Output is correct |
| 9 |
Correct |
63 ms |
38472 KB |
Output is correct |
| 10 |
Correct |
83 ms |
38340 KB |
Output is correct |
| 11 |
Correct |
74 ms |
23368 KB |
Output is correct |
| 12 |
Correct |
81 ms |
31032 KB |
Output is correct |
| 13 |
Correct |
93 ms |
23432 KB |
Output is correct |
| 14 |
Correct |
143 ms |
37724 KB |
Output is correct |
| 15 |
Correct |
146 ms |
37748 KB |
Output is correct |
| 16 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 17 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 18 |
Correct |
4 ms |
7384 KB |
Output is correct |
| 19 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 20 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 21 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 22 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 23 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 24 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 25 |
Correct |
3 ms |
7380 KB |
Output is correct |
