Submission #894851

#	Time	Username	Problem	Language	Result	Execution time	Memory
894851		qrno	Senior Postmen (BOI14_postmen)	C++17	100 / 100	459 ms	69552 KiB

postmen

/*
Solution Plan:
  Maybe just find an eulerian cycle then
  go through the cycle, if you find a vertex that was
  visited before, form a cycle with the vertices going back
  to the last appearence of the vertex
*/

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

int N, M;
vector<vector<pair<int, int>>> G;
vector<bool> used;

vector<int> path;
void dfs(int v) {
  while (!G[v].empty()) {
    auto [u, id] = G[v].back();
    G[v].pop_back();
    if (used[id]) continue;
    used[id] = true;
    dfs(u);
  }
  path.push_back(v);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> N >> M;
  G.resize(N);
  used.assign(M, false);
  for (int i = 0; i < M; i++) {
    int v, u;
    cin >> v >> u;
    v--, u--;
    G[v].push_back({u, i});
    G[u].push_back({v, i});
  }
  dfs(0);

  /* cout << "path: "; */
  /* for (auto v : path) cout << v+1 << " "; */
  /* cout << endl; */

  stack<int> S;
  vector<vector<int>> ans;

  vector<bool> seen(N);
  for (auto v : path) {
    if (seen[v]) {
      vector<int> tour;
      while (seen[v]) {
        int u = S.top();
        S.pop();
        seen[u] = false;
        tour.push_back(u);
      }
      ans.push_back(tour);
    }
    S.push(v);
    seen[v] = true;
  }

  for (auto tour : ans) {
    for (auto v : tour) cout << v+1 << ' ';
    cout << endl;
  }
}

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