Submission #733992

#	Time	Username	Problem	Language	Result	Execution time	Memory
733992		MilosMilutinovic	Senior Postmen (BOI14_postmen)	C++14	100 / 100	466 ms	77124 KiB

postmen

/**
 *    author:  wxhtzdy
 *    created: 01.05.2023 14:41:43
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<int> u(m), v(m);
  vector<vector<int>> g(n);
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i];
    --u[i]; --v[i];
    g[u[i]].push_back(i);
    g[v[i]].push_back(i);
  }
  vector<bool> rem(m);
  vector<bool> was(n);
  vector<int> ptr(n);
  vector<int> stk;
  function<void(int)> Dfs = [&](int x) {
    if (was[x]) {
      while (stk.size()) {
        int ver = stk.back();
        stk.pop_back();
        cout << ver + 1 << " ";
        was[ver] = false;
        if (ver == x) {
          break;          
        }
      }            
      cout << '\n';
    }
    stk.push_back(x);
    was[x] = true;
    for (; ptr[x] < (int) g[x].size(); ptr[x]++) {
      int e = g[x][ptr[x]];
      if (rem[e]) {
        continue;
      }
      int y = (x ^ u[e] ^ v[e]);
      rem[e] = true;
      ptr[x]++;
      Dfs(y);
      return;
    }     
    stk.pop_back();
    was[x] = false;
  };
  for (int i = 0; i < n; i++) {
    Dfs(i);
  }                                                  
  return 0;
}

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