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 <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize("unroll-loops")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation
#pragma GCC target("movbe") // byte swap
#pragma GCC target("aes,pclmul,rdrnd") // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define rep(i, a, b) for (int i = (a); i < int(b); i++) // in , ex
#define rrep(i, a, b) for (int i = (a)-1; i >= int(b); i--) // ex, in
#define pb push_back
#define all(x) x.begin(), x.end()
inline void fast()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const ll INF = 100000000000000000; // 1e17
const ll MOD = 1e9 + 7;
//
random_device rd;
mt19937 rng(rd());
template <typename T>
inline T randint(T lo, T hi) { return uniform_int_distribution<T>(lo, hi)(rng); }
#define int ll
#define float double
//
int N, M, K;
vector<int> nk;
vector<vector<int>> graph;
vector<array<array<array<array<array<ll, 2>, 2>, 2>, 2>, 2>> dp;
ll rec(int nat, int k1, int k2, int k3, int k4, int k5)
{
if (dp[nat][k1][k2][k3][k4][k5] != -1)
return dp[nat][k1][k2][k3][k4][k5];
ll ret = 1;
for (int u : graph[nat])
{
if (nk[u] == 1 && k1 == 0)
ret += rec(u, 1, k2, k3, k4, k5);
else if (nk[u] == 2 && k2 == 0)
ret += rec(u, k1, 1, k3, k4, k5);
else if (nk[u] == 3 && k3 == 0)
ret += rec(u, k1, k2, 1, k4, k5);
else if (nk[u] == 4 && k4 == 0)
ret += rec(u, k1, k2, k3, 1, k5);
else if (nk[u] == 5 && k5 == 0)
ret += rec(u, k1, k2, k3, k4, 1);
}
return dp[nat][k1][k2][k3][k4][k5] = ret;
}
int32_t main()
{
fast();
cin >> N >> M >> K;
nk.assign(N, -1);
rep(i, 0, N) cin >> nk[i];
graph.assign(N, {});
int a, b;
rep(i, 0, M)
{
cin >> a >> b;
a--;
b--;
graph[a].pb(b);
graph[b].pb(a);
}
ll ans = 0;
dp.resize(N);
// Set all values to -1
for (auto &arr1 : dp)
{
for (auto &arr2 : arr1)
{
for (auto &arr3 : arr2)
{
for (auto &arr4 : arr3)
{
for (auto &arr5 : arr4)
{
for (auto &value : arr5)
{
value = -1;
}
}
}
}
}
}
rep(i, 0, N)
{
if (nk[i] == 1)
ans += rec(i, 1, 0, 0, 0, 0);
else if (nk[i] == 2)
ans += rec(i, 0, 1, 0, 0, 0);
else if (nk[i] == 3)
ans += rec(i, 0, 0, 1, 0, 0);
else if (nk[i] == 4)
ans += rec(i, 0, 0, 0, 1, 0);
else
ans += rec(i, 0, 0, 0, 0, 1);
}
ans -= N;
cout << ans << "\n";
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... |