Submission #1304197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304197		joejoemama	Senior Postmen (BOI14_postmen)	C++20	0 / 100	392 ms	327680 KiB

postmen

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

vector<int> et = {};

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

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

    if (i == xs.size() -1) {
      while (s.size() > 0) {
        cout << s.top()+1 << " ";
        // et.push_back(s.top());
        s.pop();
      }
      cout << "\n";
    } else if (lx.find(x) != lx.end() && lx[x]) {
      while (true) {
        int y = s.top();
        cout << y+1 << " ";
        if (y == x) {
          break;
        } else {
          lx[y] = false;
          s.pop();
        }
      }
      cout << "\n";
    } else {
      lx[x] = true;
      s.push(x);
    }
  }
}

void dfs(vector<unordered_set<int>> &to, int i) {
  stack<int> s;
  s.push(i);

  while (s.size()) {
    int i = s.top();
    if (to[i].size()) {
      int j = *to[i].begin();
      to[i].erase(j);
      to[j].erase(i);
      s.push(j);
    } else {
      et.push_back(i);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  
  int n, m;
  cin >> n >> m;
  // n = 10;
  // m = 10;
  // n = 250000;
  // m = 250000;
  // n = 250000;

  vector<unordered_set<int>> to(n, unordered_set<int> {});
  et.reserve(m);

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

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

  dfs(to, 0);

  // vector<int> et;
  // for (int i = 0; i < n; i++) {
  //   et.push_back(i);
  // }
  // for (int i = n-1; i >= 0; i--) {
  //   et.push_back(i);
  // }

  clean(et);

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

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