Submission #1207580

#TimeUsernameProblemLanguageResultExecution timeMemory
1207580madamadam3Duathlon (APIO18_duathlon)C++20
5 / 100
1096 ms11332 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int const int MAXN = 100'001, MAXM = 200'001; int n, m; vector<int> adj[MAXN]; int sz[MAXN], tin[MAXN], low[MAXN], par[MAXN]; bool vis[MAXN]; bool dfs(int u1, int u2, vector<bool> &vis, int target) { if (u1 == target && u2 == target) { return true; } if (u1 != target) vis[u1] = true; if (u2 != target) vis[u2] = true; if (u1 == target && u2 != target) { for (int v2 : adj[u2]) { if (vis[v2]) continue; if (dfs(u1, v2, vis, target)) return true; } } else if (u1 != target && u2 == target) { for (int v1 : adj[u1]) { if (vis[v1]) continue; if (dfs(v1, u2, vis, target)) return true; } } else { for (int v1 : adj[u1]) { if (vis[v1]) continue; for (int v2 : adj[u2]) { if (vis[v2]) continue; if (v1 == v2 && v1 != target) continue; if (dfs(v1, v2, vis, target)) return true; } } } if (u1 != target) vis[u1] = false; if (u2 != target) vis[u2] = false; return false; } signed main() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int ways = 0; for (int s = 1; s <= n; s++) { for (int c = 1; c <= n; c++) { if (c == s) continue; for (int f = 1; f <= n; f++) { if (f == c || f == s) continue; vector<bool> vis(n+1, false); if (dfs(s, f, vis, c)) { ways++; // cout << "(" << s << ", " << c << ", " << f << ") works\n"; } } } } cout << ways; 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...
#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...