Submission #519719

#TimeUsernameProblemLanguageResultExecution timeMemory
519719MonarchuwuAmusement Park (CEOI19_amusementpark)C++17
7 / 100
1 ms204 KiB
#include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define ff first #define ss second const int N = 20, M = 400, mod = 998244353; int n, m; pii edge[M]; vector<int> g[N]; void loadGraph(int mask) { for (int i = 1; i <= n; ++i) g[i].clear(); for (int i = 0; i < m; ++i) if (mask >> i & 1) g[edge[i].ss].push_back(edge[i].ff); else g[edge[i].ff].push_back(edge[i].ss); } int vis[N]; bool dfs(int u) { vis[u] = 1; for (int v : g[u]) if ((!vis[v] && dfs(v)) || vis[v] == 1) return true; vis[u] = 2; return false; } bool check() { fill(vis + 1, vis + n + 1, 0); for (int i = 1; i <= n; ++i) if (!vis[i] && dfs(i)) return false; return true; } int lg[N]; int main() { cin.tie(NULL)->sync_with_stdio(false); cin >> n >> m; for (int i = 0; i < m; ++i) cin >> edge[i].ff >> edge[i].ss; ll cnt(0); for (int mask = 0; mask < (1 << m); ++mask) { lg[mask] = lg[mask >> 1] + (mask & 1); loadGraph(mask); if (check()) cnt += lg[mask]; } cout << cnt % mod << '\n'; } /** /\_/\ * (= ._.) * / >0 \>1 **/
#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...