제출 #122905

#제출 시각아이디문제언어결과실행 시간메모리
122905miguelPaths (BOI18_paths)C++14
100 / 100
570 ms100484 KiB
#include<bits/stdc++.h> using namespace std; #define rc(x) return cout<<x<<endl,0 #define pb push_back #define dbg(x) cout << #x << '=' << x << '\n'; #define ll long long #define sz size() #define x first #define y second #define pi pair <int, int> #define pii pair <pi, int> #define vi vector <int> const ll mod = 1000000007; #define int ll int n, m, k, c[300001], dp[300001][32]; vector <int> g[300001]; int gcd(int a, int b){ if(a==0) return b; else return gcd(b%a, a); } int32_t main(){ ios_base :: sync_with_stdio(0); cin.tie(); cout.tie(); cin>>n>>m>>k; for(int i=1; i<=n; i++){ cin>>c[i]; c[i]--; } for(int i=1; i<=m; i++){ int x, y; cin>>x>>y; g[x].pb(y); g[y].pb(x); } for(int i=1; i<=n; i++) dp[i][(1<<c[i])]=1; for(int mask=1; mask<(1<<k); mask++){ for(int i=1; i<=n; i++){ if(dp[i][mask]==0) continue; for(int j: g[i]){ if(((1<<c[j])&mask)) continue; else dp[j][(mask|(1<<c[j]))]+=dp[i][mask]; } } } int ans=0; for(int mask=1; mask<(1<<k); mask++){ for(int i=1; i<=n; i++){ //if(dp[i][mask]) cout<<i<<" "<<mask<<" "<<dp[i][mask]<<endl; ans+=dp[i][mask]; } } cout<<ans-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...