Submission #703585

#TimeUsernameProblemLanguageResultExecution timeMemory
703585sheldonSenior Postmen (BOI14_postmen)C++17
0 / 100
7 ms14036 KiB
#include <bits/stdc++.h> using namespace std; const int nax = 5e5 + 5; vector<pair<int, int>> edges[nax]; int deg[nax], where[nax]; bool used[nax]; void solve() { int n, m; cin >> n >> m; for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; ++deg[u], ++deg[v]; edges[u].push_back({v, i}); edges[v].push_back({u, i}); } vector<int> st = {1}, ans; int at = 1; while (!st.empty()) { if (deg[at]) { st.push_back(at); while (used[edges[at].back().second]) { edges[at].pop_back(); } --deg[at]; used[edges[at].back().second] = 1; at = edges[at].back().first; --deg[at]; } else { ans.push_back(at); at = st.back(); st.pop_back(); } } vector<pair<int, int>> stt; for (int i = 0; i < nax; ++i) { where[i] = -1; } for (int i = 0; i < ans.size(); ++i) { stt.push_back({ans[i], i}); if (where[ans[i]] != -1) { int x = where[ans[i]]; while (stt.back().second > x) { where[stt.back().first] = -1; cout << stt.back().first << ' '; stt.pop_back(); } where[ans[i]] = stt.back().second; cout << ans[i] << '\n'; } else { where[ans[i]] = i; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); }

Compilation message (stderr)

postmen.cpp: In function 'void solve()':
postmen.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < ans.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...