Submission #805266

#	Time	Username	Problem	Language	Result	Execution time	Memory
805266		tch1cherin	Senior Postmen (BOI14_postmen)	C++17	100 / 100	332 ms	44464 KiB

postmen

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<vector<pair<int, int>>> G(N);
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].push_back({v, i});
    G[v].push_back({u, i});
  }
  vector<int> ptr(N);
  vector<bool> used(M);
  vector<int> path;
  stack<int> s;
  s.push(0);
  while (!s.empty()) {
    int u = s.top();
    while (ptr[u] < (int)G[u].size() && used[G[u][ptr[u]].second]) {
      ptr[u]++;
    }
    if (ptr[u] == (int)G[u].size()) {
      path.push_back(u);
      s.pop();
    } else {
      used[G[u][ptr[u]].second] = true;
      s.push(G[u][ptr[u]++].first);
    }
  }
  vector<bool> occ(N, false);
  vector<vector<int>> cycles;
  vector<int> b;
  for (int v : path) {
    b.push_back(v);
    if (occ[v]) {
      cycles.push_back({});
      cycles.back().push_back(v);
      b.pop_back();
      while (b.back() != v) {
        cycles.back().push_back(b.back());
        occ[b.back()] = false;
        b.pop_back();
      }
    } else {
      occ[v] = true;
    }
  }
  for (auto cycle : cycles) {
    int k = (int)cycle.size();
    for (int i = 0; i < k; i++) {
      cout << 1 + cycle[i] << " \n"[i + 1 == k];
    }
  }
}

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