This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Bismi Allah
#include "bits/stdc++.h"
using namespace std;
#define int long long
signed main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m, k, ans = 0;
cin >> n >> m >> k;
vector <int> color(n), g[n], used(n), permutation;
set <int> colorUsed;
set <vector <int>> paths;
vector <int> path;
function <void(int, int)> dfs=[&](int v, int cur) {
//path.push_back(v);
//if(paths.count(path) == 0 && path.size() > 1) ans ++, paths.insert(path);
if(cur == permutation.size() - 1) {
ans++;
return;
}
used[v] = 1;
for(auto u : g[v] ) {
if(!used[u] && color[u] == permutation[cur+1]) dfs(u, cur + 1);
}
path.pop_back();
used[v]=0;
};
for(int i = 0; i < n; i ++) cin >> color[i];
for(int i = 0; i < m; i ++) {
int u, v;
cin >> u >> v;
u --, v --;
g[u].push_back(v);
g[v].push_back(u);
}
permutation.resize(k);
for(int i = 0; i < k; i ++) permutation[i] = i + 1;
do {
for(int i = 0; i < n; i ++) {
if(color[i] == permutation[0]) dfs(i, 0);
}
}while(next_permutation(permutation.begin(), permutation.end()));
cout << ans;
return 0;
}
Compilation message (stderr)
paths.cpp: In lambda function:
paths.cpp:20:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | if(cur == permutation.size() - 1) {
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |