This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, x, c[105], factorial[5] = {1, 1, 2, 6, 24};
bool adj[105][105];
int validPaths(vector<int> path) {
int sz = path.size();
for (int i = 0; i < sz; i++) {
for (int j = i + 1; j < sz; j++) {
if (c[path[i]] == c[path[j]]) return 0;
}
}
int ans = 0;
for (int i = 0; i < factorial[sz]; i++) {
bool connected = 1;
for (int j = 1; j < sz; j++) {
connected &= adj[path[j - 1]][path[j]];
}
ans += connected;
next_permutation(path.begin(), path.end());
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> x;
for (int i = 0; i < n; i++) {
cin >> c[i];
}
while (m--) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u][v] = adj[v][u] = 1;
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (x >= 2) {
for (int j = i + 1; j < n; j++) {
ans += validPaths({i, j});
if (x >= 3) {
for (int k = j + 1; k < n; k++) {
ans += validPaths({i, j, k});
if (x >= 4) {
for (int l = k + 1; l < n; l++) {
ans += validPaths({i, j, k, l});
}
}
}
}
}
}
}
cout << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |