제출 #1216433

#제출 시각아이디문제언어결과실행 시간메모리
1216433HasanV11010238Paths (BOI18_paths)C++20
100 / 100
364 ms66324 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; #define mod 998244353 #define MAX 2000 int main(){ ll n, m, k, a, b; cin>>n>>m>>k; vector<vector<int>> v(n + 1); vector<int> col(n + 1, 0); for (int i = 1; i <= n; i++){ cin>>col[i]; col[i]--; } for (int i = 0; i < m; i++){ cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } int ti = (1<<k); vector<vector<ll>> dp(n + 1, vector<ll>(ti, 0)); for (int i = 1; i <= n; i++){ dp[i][(1<<col[i])]++; } for (int i = 0; i < ti; i++){ for (int j = 1; j <= n; j++){ for (auto el : v[j]){ int val = i & (1<<col[el]); if (val != 0) continue; int to = i | (1<<col[el]); dp[el][to] += dp[j][i]; } } } ll ans = 0; for (int i = 1; i <= n; i++){ for (int j = 0; j < ti; j++) ans += dp[i][j]; } cout<<ans - n<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...