Submission #1288858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288858		peterandvoi	Senior Postmen (BOI14_postmen)	C++20	100 / 100	438 ms	86276 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<int> deg(n);
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    ++deg[u], ++deg[v];
    g[u].push_back({v, i});
    g[v].push_back({u, i});
  }
  for (int i = 0; i < n; ++i) {
    assert(deg[i] % 2 == 0);
  }
  vector<int> res;
  vector<bool> used(m);
  auto dfs = [&](auto self, int u) -> void {
    while (g[u].size()) {
      auto [v, id] = g[u].back();
      g[u].pop_back();
      if (used[id]) {
        continue;
      }
      used[id] = 1;
      self(self, v);
    }
    res.push_back(u);
  };
  dfs(dfs, 0);
  assert((int) res.size() == m + 1);
  vector<bool> in(n);
  vector<int> st;
  vector<vector<int>> cyc;
  for (int i = 0; i <= m; ++i) {
    if (in[res[i]]) {
      cyc.push_back({res[i]});
      while (st.size() && st.back() != res[i]) {
        cyc.back().push_back(st.back());
        in[st.back()] = 0;
        st.pop_back();
      } 
    } else {
      in[res[i]] = 1;
      st.push_back(res[i]);
    }
  }
  assert((int) st.size() == 1 && st[0] == 0);
  for (auto &v : cyc) {
    for (int u : v) {
      cout << u + 1 << " ";
    }
    cout << "\n";
  }
}

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45