Submission #519715

#TimeUsernameProblemLanguageResultExecution timeMemory
519715MonarchuwuAmusement Park (CEOI19_amusementpark)C++17
0 / 100
1 ms256 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; int n, m; pii edge[N]; 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, int tme) { vis[u] = tme; for (int v : g[u]) { if (!vis[v]) dfs(v, tme); else if (vis[v] == tme) return true; } return false; } bool check() { fill(vis + 1, vis + n + 1, 0); for (int i = 1; i <= n; ++i) if (!vis[i] && dfs(i, 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; int 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 << '\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...