제출 #1269988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269988		rtri	어르신 집배원 (BOI14_postmen)	C++20	0 / 100	175 ms	327680 KiB

postmen

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

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

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

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

  for (auto [v, edg] : adj[u]) {
    if (!used[edg] && v != p) {
      if (dfs(v, time, 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, -1);
  vector<vector<int>> sols;
  for (int i = 0; i < m; i++) {
    if (dfs(edgtojun[i], 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: 0 / 38
• Subtask 2: 0 / 17
• Subtask 3: 0 / 45