oj.uz

Submission #894849

# Submission time Handle Problem Language Result Execution time Memory
894849 2023-12-29T05:53:59 Z qrno Senior Postmen (BOI14_postmen) C++17
0 / 100
 1 ms 348 KB 
/*
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);

  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);
    } else {
      seen[v] = true;
    }
    S.push(v);
  }

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

Subtask #1
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Some edges were not used
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Some edges were not used
4 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 0 ms 348 KB Some edges were not used
4 Halted 0 ms 0 KB -