Submission #1173599

#TimeUsernameProblemLanguageResultExecution timeMemory
1173599AlgorithmWarriorPaths (BOI18_paths)C++20
100 / 100
362 ms99856 KiB
#include <bits/stdc++.h> using namespace std; int const MAX=3e5+5; long long dp[MAX][35]; vector<int>G[MAX]; int n,m,k; int color[MAX]; void read(){ cin>>n>>m>>k; int i; for(i=1;i<=n;++i){ cin>>color[i]; --color[i]; dp[i][1<<color[i]]=1; } for(i=1;i<=m;++i){ int u,v; cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } } long long get_dp(){ long long sum=0; int i,j; for(j=1;j<(1<<k);++j){ for(i=1;i<=n;++i) if(j&(1<<color[i])){ for(auto vec : G[i]) dp[i][j]+=dp[vec][j^(1<<color[i])]; sum+=dp[i][j]; } } return sum-n; } int main() { read(); cout<<get_dp(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...