제출 #1188652

#제출 시각아이디문제언어결과실행 시간메모리
1188652petezaPaths (BOI18_paths)C++20
100 / 100
261 ms92756 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int n, m, k, a, b; ll dp[300005][1<<5]; vector<int> adj[300005]; int col[300005]; int main() { cin.tie(0) -> sync_with_stdio(0); cin >> n >> m >> k; for(int i=1;i<=n;i++) { cin >> col[i]; col[i]--; dp[i][1<<col[i]] = 1; } while(m--) { cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } ll sum = 0; for(int cst = 0; cst < (1 << k); cst++) { for(int i=1;i<=n;i++) { for(auto &e:adj[i]) { if((cst >> col[e]) & 1) continue; dp[e][cst | (1 << col[e])] += dp[i][cst]; } sum += dp[i][cst]; //cout << dp[i][cst] << ' '; } //cout << '\n'; } cout << sum-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...