Submission #1188344

#TimeUsernameProblemLanguageResultExecution timeMemory
1188344kl0989ePaths (BOI18_paths)C++20
100 / 100
230 ms104452 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pb push_back #define vi vector<int> #define vl vector<ll> #define pi pair<int, int> #define pl pair<ll,ll> #define all(x) (x).begin(),(x).end() const int maxn=3e5+10; vector<vl> dp(maxn,vl(1<<5,0)); vi col(maxn); vector<vi> graph(maxn); int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n,m,k; cin >> n >> m >> k; for (int i=0; i<n; i++) { cin >> col[i]; col[i]--; dp[i][1<<col[i]]=1; } int a,b; for (int i=0; i<m; i++) { cin >> a >> b; graph[--a].pb(--b); graph[b].pb(a); } ll ans=0; for (int msk=3; msk<(1<<k); msk++) { if (__builtin_popcount(msk)==1) { continue; } for (int i=0; i<n; i++) { if (!(msk&(1<<col[i]))) { continue; } for (auto to:graph[i]) { dp[i][msk]+=dp[to][msk^(1<<col[i])]; } ans+=dp[i][msk]; } } cout << ans << '\n'; 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...