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
void do_another(int n, int m, int k, int ans) {
int changes = 1;
vector <int> color(n), g[n], used(n), permutation(k);
set <int> colorUsed;
function <void(int, int)> dfs=[&](int v, int cur) {
if(cur >= changes) {
ans++;
}
if(cur == permutation.size() - 1) return;
used[v] = 1;
for(auto u : g[v] ) {
if(!used[u] && color[u] == permutation[cur+1]) dfs(u, cur + 1);
}
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);
}
vector <int> prev;
for(int i = 0; i < k; i ++) permutation[i] = i + 1;
do{
if(prev.size() > 0) {
for(int i = 0; i < permutation.size(); i ++) {
if(prev[i] != permutation[i]) {
changes = i;
break;
}
}
changes = max(changes, 1LL);
}
for(int i = 0; i < n; i ++) {
if(color[i] == permutation[0]) dfs(i, 0);
}
prev = permutation;
} while(next_permutation(permutation.begin(), permutation.end()));
cout << ans;
exit(0);
}
signed main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m, k, ans = 0;
cin >> n >> m >> k;
if(k > 3) {
do_another(n, m, k, ans);
return 0;
}
vector <int> color(n), g[n];
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);
}
for(int i = 0; i < n; i ++) {
for(auto u : g[i]) {
if(color[i] != color[u]) ans ++;
}
int color1 = 0, color2 = 0, forOne = -1;
for(auto u : g[i]) {
if(color[u] == color[i]) continue;
if(forOne == -1) {
forOne = color[u];
color1 ++;
}else {
if(forOne == color[u]) color1 ++;
else color2 ++;
}
}
ans += 2 * color1 * color2;
}
cout << ans;
return 0;
}
Compilation message (stderr)
paths.cpp: In lambda function:
paths.cpp:16: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]
16 | if(cur == permutation.size() - 1) return;
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp: In function 'void do_another(long long int, long long int, long long int, long long int)':
paths.cpp:36:21: 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]
36 | for(int i = 0; i < permutation.size(); i ++) {
| ~~^~~~~~~~~~~~~~~~~~~~
# | 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... |