제출 #1265962

#제출 시각아이디문제언어결과실행 시간메모리
1265962warrennPaths (BOI18_paths)C++20
100 / 100
432 ms96024 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int n,m,k; int dp[300002][32]; int col[300002]; vector<int>adj[300002]; signed main(){ cin>>n>>m>>k; for(int q=1;q<=n;q++){ cin>>col[q]; col[q]--; dp[q][(1<<col[q])]=1; } for(int q=1;q<=m;q++){ int u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } int ans=0; for(int mask=0;mask<(1<<k);mask++){ for(int idx=1;idx<=n;idx++){ for(auto nxt : adj[idx]){ if((mask>>col[nxt])&1){ } else{ dp[nxt][mask+(1<<col[nxt])]+=dp[idx][mask]; } } ans+=dp[idx][mask]; } } cout<<ans-n<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...