Submission #989040

#TimeUsernameProblemLanguageResultExecution timeMemory
989040AlphaMale06Paths (BOI18_paths)C++17
100 / 100
289 ms100432 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 3e5+3; int dp[N][32]; vector<int> g[N]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; int col[n]; for(int i=0; i< n; i++){ cin >> col[i]; col[i]--; col[i]=1<<col[i]; } for(int i=0; i< m; i++){ int a, b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } for(int i=0; i< n; i++){ dp[i][col[i]]=1; } vector<int> maske[k]; for(int i=1; i< (1<<k); i++){ int pcnt = __builtin_popcount(i); maske[pcnt-1].push_back(i); } for(int j=0; j<k; j++){ for(int i=0; i< n; i++){ for(int mask : maske[j]){ for(int to : g[i]){ if(col[to] & mask)continue; dp[to][mask+col[to]]+=dp[i][mask]; } } } } int ans=0; for(int i=1; i< (1<<k); i++){ for(int j=0; j< n; j++)ans+=dp[j][i]; } 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...