Submission #1207429

#TimeUsernameProblemLanguageResultExecution timeMemory
1207429Trn115지도 색칠하기 (GA3_map)C++20
85 / 120
1594 ms420 KiB
#include <bits/stdc++.h> #define int long long using namespace std; inline int getbit(int x, int i) { return (x >> (i - 1)) & 1; } inline void invertbit(int &x, int i) { x ^= (1 << (i - 1)); } long long NumberOfMaps (signed N, signed M, signed *A, signed *B) { vector<vector<int>> g(N + 1); for (int i = 0; i < M; ++i) { g[A[i]].push_back(B[i]); g[B[i]].push_back(A[i]); } int si = 1LL << N; int res = 0, mask; vector<int> color; bool sat[2]; function<void(int, int, int)> dfs = [&](int v, int c, int type) { color[v] = c; for (int u : g[v]) { if (getbit(mask, u) != type) continue; if (color[u] == -1) { dfs(u, c ^ 1, type); } else if (color[u] == c) { sat[type] = false; } } }; for (mask = 0; mask < si; ++mask) { color.assign(N + 1, -1); int cc = 0; sat[0] = sat[1] = true; for (int i = 1; i <= N; ++i) { if (getbit(mask, i) == 0 && color[i] == -1) { dfs(i, 0, 0); ++cc; } } for (int i = 1; i <= N; ++i) { if (getbit(mask, i) == 1 && color[i] == -1) { dfs(i, 0, 1); ++cc; } } if (sat[0] && sat[1]) res += 1LL << cc; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...