Submission #1034643

#TimeUsernameProblemLanguageResultExecution timeMemory
1034643anangoPaths (BOI18_paths)C++17
100 / 100
387 ms62292 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int INF = 1LL<<30; signed main() { #ifdef ONLINE_JUDGE ios_base::sync_with_stdio(false); cin.tie(NULL); #endif //fast IO int n,m,k; cin >> n >> m >> k; vector<vector<int>> adjlist(n); vector<int> col(n); for (int i=0; i<n; i++) {cin >> col[i]; col[i]--;} for (int i=0; i<m; i++) { int u,v; cin >> u >> v; u--; v--; adjlist[u].push_back(v); adjlist[v].push_back(u); } int dp[n][1<<k]; for (int i=0; i<n; i++) { for (int j=0; j<1<<k; j++) { dp[i][j] = 0; } } //dp[i][j] = number of paths with this bitmask of colours used, ending in this vertex for (int i=0; i<n; i++) { dp[i][1<<col[i]]++; } for (int mask=1; mask<1<<k; mask++) { for (int i=0; i<n; i++) { if (mask&(1<<col[i])==0) continue; for (int j:adjlist[i]) { dp[i][mask]+=dp[j][mask^(1<<col[i])]; } } } int su=0; for (int i=0; i<n; i++) { for (int j=0; j<1<<k; j++) { su+=dp[i][j]; } } cout << su-n << endl; }

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:30:33: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   30 |             if (mask&(1<<col[i])==0) continue;
      |                      ~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...