# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
823109 |
2023-08-12T08:11:27 Z |
Desh03 |
Paths (BOI18_paths) |
C++17 |
|
3000 ms |
3084 KB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g, cnt;
vector<int> c;
vector<bool> vis;
void dfs(int u, int mask, const bool &z) {
vis[u] = 1;
++cnt[z][mask];
for (int v : g[u]) {
if (!vis[v] && !(mask >> c[v] & 1)) {
dfs(v, mask | (1 << c[v]), z);
}
}
vis[u] = 0;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
g.resize(n), cnt.resize(2, vector<int> (1 << k)), c.resize(n), vis.resize(n);
for (int i = 0; i < n; i++) {
cin >> c[i];
--c[i];
}
long long ans = 0;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
--u, --v;
vis[v] = 1;
dfs(u, 1 << c[u], 0);
vis[u] = 1;
dfs(v, 1 << c[v], 1);
vis[u] = 0;
for (int mask = 0; mask < (1 << k); mask++) {
for (int mask2 = 0; mask2 < (1 << k); mask2++) {
if ((mask & mask2) == 0) {
ans += cnt[0][mask] * cnt[1][mask2] << 1;
}
}
}
for (int j : {0, 1})
for (int &x : cnt[j]) x = 0;
g[u].push_back(v);
g[v].push_back(u);
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
320 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3040 ms |
3084 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
320 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Execution timed out |
3040 ms |
3084 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Execution timed out |
3036 ms |
516 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |