Submission #1304193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304193		joejoemama	어르신 집배원 (BOI14_postmen)	C++20	55 / 100	1046 ms	158984 KiB

postmen

// https://oj.uz/problem/view/BOI14_postmen
#include <bits/stdc++.h>
#include <ios>
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 i = 0; i < xs.size(); i++) {
    int x = xs[i];

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

      while (s.size() > 0) {
        et.push_back(s.top());
        s.pop();
      }

      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);
        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() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  
  int n, m;
  cin >> n >> m;
  // n = 250000;

  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);

  // 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: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45