Submission #1233312

#TimeUsernameProblemLanguageResultExecution timeMemory
1233312zyadhanySenior Postmen (BOI14_postmen)C++20
55 / 100
311 ms327680 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> #define ll int #define ld long double #define pl pair<ll, ll> #define vi vector<ll> #define vii vector<vi> #define vc vector<char> #define vcc vector<vc> #define vp vector<pl> #define mi map<ll,ll> #define mc map<char,int> #define sortx(X) sort(X.begin(),X.end()); #define all(X) X.begin(),X.end() #define allr(X) X.rbegin(),X.rend() #define ln '\n' #define YES {cout << "Alice\n"; return;} #define NO {cout << "Bob\n"; return;} #define MUN {cout << "-1\n"; return;} const int MODE = 1e9 + 7; using namespace std; /* eulerian circuit: that path start and end at the same vertex and visits every edge exactly once. eulerian path: that path may start and end at different vertices and visits every edge exactly once. in an undirected graph: - an eulerian circuit exists if and only if every vertex has even degree and the graph is connected. - an eulerian path if it's eulerian circuit or if it has exactly two vertices with odd degree and the graph is connected. in directed graph: - an eulerian circuit exists if and only if every vertex has equal in-degree and out-degree and the graph is strongly connected. - an eulerian path exists if it has exactly one vertex with (out-degree - in-degree) = 1, exactly one vertex with (in-degree - out-degree) = 1, and all other vertices have equal indegree and out-degree. */ class Graph { public: int size; vp Edge; vii adj; bool isConnected() { ll summ = 0, n = 0, src = -1; vi visited(size + 1); stack<int> stack; for (int i = 0; i < adj.size(); i++) if (!adj[i].empty()) n++, src = i; if (src != -1) stack.push(src); while (!stack.empty()) { int m = stack.top(); stack.pop(); if (visited[m]) continue; visited[m] = 1, summ++; for (auto a : adj[m]) if (!visited[a]) stack.push(a); } return (summ == n); } /* The function returns one of the following values 0 --> If graph is not Eulerian 1 --> If graph has an Euler path (Semi-Eulerian) 2 --> If graph has an Euler Circuit (Eulerian) */ int isEulerian() { if (!isConnected()) return 0; int odd = 0; for (int i = 0; i <= size; i++) odd += (adj[i].size() & 1); if (odd > 2) return 0; return (odd)? 1 : 2; } vii EulerPath(ll src) { vii X; stack<ll> st; st.push(src); vector<deque<pl>> Y(size + 1); vi visted(Edge.size()); for (int i = 0; i < Edge.size(); i++) { int u = Edge[i].first, v = Edge[i].second; Y[u].push_back({v, i}); Y[v].push_back({u, i}); } stack<ll> tm; vi ontm(size + 10); while (!st.empty()) { ll m = st.top(); bool isit = 1; while (!Y[m].empty()) { pl at = Y[m].front(); Y[m].pop_front(); if (visted[at.second]) continue; visted[at.second] = 1; st.push(at.first); isit = 0; break; } if (isit) { if (ontm[m]) { vi Y; while (ontm[m]) { ll tp = tm.top(); ontm[tp] = 0; Y.push_back(tp); tm.pop(); } X.push_back(Y); } tm.push(m); ontm[m] = 1; st.pop(); } } reverse(all(X)); return (X); } void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); Edge.push_back({u, v}); } Graph(ll n) { size = n; adj.resize(n + 1); } }; void solve(int tc) { ll n, m; cin >> n >> m; Graph gr(n+1); for (int i = 0; i < m; i++) { ll u, v; cin >> u >> v; gr.addEdge(u, v); } auto res = gr.EulerPath(1); for (auto Z : res) { for (auto a : Z) cout << a << ' '; cout << '\n'; } } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int size = 1; //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); // cin >> size; for (int i = 1; i <= size; i++) solve(i); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...