Submission #861245

#TimeUsernameProblemLanguageResultExecution timeMemory
861245qwushaSenior Postmen (BOI14_postmen)C++17
55 / 100
1040 ms226288 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second typedef long double ld; const ll inf = 1e9; const ld eps = 1e-8; vector<map<int, int>> cing; vector<set<int>> g; vector<vector<int>> ans; vector<bool> used; vector<int> cur; set<int> stcur; set<pair<int, int>> vert; void dfs(int v) { if (stcur.find(v) != stcur.end()) { vector<int> res; while(cur.back() != v) { stcur.erase(cur.back()); res.push_back(cur.back()); cur.pop_back(); } stcur.erase(cur.back()); res.push_back(cur.back()); cur.pop_back(); ans.push_back(res); } cur.push_back(v); stcur.insert(v); if(!g[v].empty()) { auto t = g[v].begin(); int u = *t; g[v].erase(u); g[u].erase(v); dfs(u); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; used.resize(n); g.resize(n); cing.resize(n); for (int i = 0; i < m; i++) { int v, u; cin >> v >> u; if (v > u) swap(u, v); cing[v - 1][u - 1]++; } for (int v = 0; v < n; v++) { for (auto [u, cn] : cing[v]) { while (cn > 1) { cn -= 2; ans.push_back({v, u}); } if (cn == 1) { g[v].insert(u); g[u].insert(v); vert.insert({v, u}); vert.insert({u, v}); } } } for (int i = 0; i < n; i++) { dfs(i); } for (auto s : ans) { for (auto el : s) { cout << el + 1 << ' '; } cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...