Submission #1304191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304191		joejoemama	Senior Postmen (BOI14_postmen)	C++20	55 / 100	1101 ms	159016 KiB

postmen

// https://oj.uz/problem/view/BOI14_postmen
#include <bits/stdc++.h>
using namespace std;

vector<int> et = {};
vector<vector<int>> ets = {};

void clean(vector<int> xs) {
  unordered_map<int, bool> lx;

  stack<int> s;

  // for (int x : xs) {
  //   cout << x << " ";
  // }
  // cout << endl;

  for (int i = 0; i < xs.size(); i++) {
    int x = xs[i];
    // cout << i << " " << x << endl;

    if (i == xs.size() -1) {
      vector<int> et = {};

      while (s.size() > 0) {
        et.push_back(s.top());
        // cout << s.top() << endl;
        s.pop();
      }
      // cout << "A" << endl;

      ets.push_back(et);
    } else if (lx.find(x) != lx.end() && lx[x]) {
      vector<int> oxs = {x, };
      while (true) {
        int y = s.top();
        oxs.push_back(y);
        // cout << y << endl;
        if (y == x) {
          break;
        } else {
          lx[y] = false;
          s.pop();
        }
      }

      clean(oxs);
    } else {
      lx[x] = true;
      s.push(x);
    }
  }
}

void dfs(vector<unordered_set<int>> &to, int i) {
  while (to[i].size()) {
    int j = *to[i].begin();
    to[i].erase(j);
    to[j].erase(i);

    dfs(to, j);
  }
  et.push_back(i);
}

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

  vector<unordered_set<int>> to(n, unordered_set<int> {});

  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;

    to[a].insert(b);
    to[b].insert(a);
  }

  dfs(to, 0);

  // for (int a : et) {
  //   cout << a+1 << " ";
  // }
  // cout << endl;

  clean(et);

  for (auto et : ets) {
    // cout << "B" << endl;
    for (int x : et) {
      cout << x+1 << " ";
    }
    cout << endl;
  }
}

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