Submission #1050625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050625		makanhulia	Senior Postmen (BOI14_postmen)	C++17	0 / 100	1094 ms	11812 KiB

postmen

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

#define debug(x) cout << #x << ": " << x << endl;
#define all(x) x.begin(), x.end()
#define int long long

void g(vector<int> a) {
  for (auto el : a) cout << el+1 << ", ";
  cout << endl;
}

void solve() {
  int n,m;cin>>n>>m;
  vector<set<int>> adj(n, set<int>());

  for (int i = 0; i < m; i++) {
    int u,v;cin>>u>>v;u--;v--;
    adj[u].insert(v);
    adj[v].insert(u);
  }

  vector<vector<int>> ans;
  for (int i = 0; i < n; i++) {
    while (!adj[i].empty()) {
      map<int, int> p;
      p[i] = i;
      queue<int> q;
      q.push(i);
      vector<int> hist1, hist2;
      function<void(int, vector<int>*)> gethist = [&](int node, vector<int>* zz) {
        zz->push_back(node);
        if (p[node] == node) return;
        gethist(p[node], zz);
      };
      while (!q.empty()) {
        int node = q.front();q.pop();
        for (auto children : adj[node]) {
          if (children == p[node]) continue;

          if (!p.count(children)) p[children] = -1;
          if (p[children] != -1) {
            // found the loop
            gethist(children, &hist1);
            gethist(node, &hist2);
            goto Next;
          }

          p[children] = node;
          q.push(children);
        }
      }
      Next:;
      // debug(i);
      reverse(all(hist1));
      for (auto el : hist2) hist1.push_back(el);

      // found a loop but not this, still okay though
      for (int i = 0; i+1 < hist1.size(); i++) {
        adj[hist1[i]].erase(hist1[i+1]);
        adj[hist1[i+1]].erase(hist1[i]);
      }

      hist1.pop_back();
      ans.push_back(hist1);
    }
  }

  for (auto v : ans) {
    for (auto el : v) cout << el+1 << " ";
    cout << endl;
  }
}

int32_t main() {
  solve();
  return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'void solve()':
postmen.cpp:59:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |       for (int i = 0; i+1 < hist1.size(); i++) {
      |                       ~~~~^~~~~~~~~~~~~~

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