제출 #1269993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269993		rtri	Senior Postmen (BOI14_postmen)	C++20	38 / 100	1095 ms	15808 KiB

postmen

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

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

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);
  edgtojun.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});
    edgtojun[i] = u;
  }

  vis.resize(n);
  vector<vector<int>> sols;
  for (int i = 0; i < m; i++) {
    fill(vis.begin(), vis.end(), false);
    if (dfs(edgtojun[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