Submission #1269984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269984		rtri	Senior Postmen (BOI14_postmen)	C++20	38 / 100	1092 ms	15552 KiB

postmen

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

int used_edges = 0;
vector<bool> used;
vector<vector<pair<int, int>>> adj;

vector<bool> vis;
vector<int> sol;
bool dfs(int u, int start = -1, int p = -1) {
  if (u == start) {
    return true;
  }
  if (start == -1)
    start = u;

  if (vis[u])
    return false;
  vis[u] = 1;

  for (auto [v, edg] : adj[u]) {
    if (!used[edg] && v != p) {
      if (dfs(v, start, u)) {
        used[edg] = 1;
        used_edges++;
        sol.push_back(u);
        return true;
      }
    }
  }

  return false;
}

int main() {
  int n, m;
  cin >> n >> m;

  adj.resize(n);
  used.resize(m);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    adj[u].push_back({v, i});
    adj[v].push_back({u, i});
  }

  vis.resize(n);
  vector<vector<int>> sols;
  while (used_edges != m) {
    for (int i = 0; i < n; i++) {
      fill(vis.begin(), vis.end(), false);
      if (dfs(i)) {
        reverse(sol.begin(), sol.end());
        sols.push_back(sol);
        sol.clear();
      }
    }
  }

  for (auto sol : sols) {
    for (int idx : sol)
      cout << idx + 1 << " ";
    cout << "\n";
  }

  return 0;
}

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