제출 #1239212

#제출 시각아이디문제언어결과실행 시간메모리
1239212eirinayukariPaths (BOI18_paths)C++20
100 / 100
310 ms92836 KiB
// XD XD #include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define el cout << "\n"; using namespace std; using ll = long long; const int MAXN = 3e5 + 7; const int MAXK = 5; const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const ll LLINF = 1e18 + 7; template <typename T> bool ckmin(T& a, T b) { return a > b ? a = b, true : false; } template <typename T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; } int n, m, k; int c[MAXN]; ll dp[MAXN][1 << MAXK]; vector<int> adj[MAXN]; void dfs(int u, int mask) { if (dp[u][mask] != -1) { return; } if (mask >> c[u] & 1) { dp[u][mask] = 0; return; } int nmask = mask ^ (1 << c[u]); dp[u][mask] = 1; for (int v : adj[u]) { dfs(v, nmask); dp[u][mask] += dp[v][nmask]; } } void solve(int id) { // cout << "Case " << id << ": "; cin >> n >> m >> k; for (int i = 1; i <= n; i++) { cin >> c[i]; c[i]--; } for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } memset(dp, -1, sizeof dp); ll ans = 0; for (int i = 1; i <= n; i++) { dfs(i, 0); ans += dp[i][0] - 1; } cout << ans << "\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); int T = 1; // cin >> T; for (int i = 1; i <= T; i++) { solve(i); } 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...