Submission #1050682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050682		andecaandeci	Senior Postmen (BOI14_postmen)	C++17	38 / 100	1065 ms	28964 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;
  vector<int> vis(n);
  for (int i = 0; i < n; i++) {
    while (!adj[i].empty()) {
      vector<int> hist;
      bool ok = 0;
      function<void(int, int)> dfs = [&](int node, int p) {
        vis[node] = 1;
        hist.push_back(node);

        for (auto children : adj[node]) {
          if (children == p) continue;
          if (children == i) ok = 1;
          if (ok) break;
          if (!vis[children]) {
            dfs(children,node);
          }
        }

        vis[node] = 0;
        if (!ok) hist.pop_back();
      };
      dfs(i, -1);
      ans.push_back(hist);
      for (int i = 0; i < hist.size(); i++) {
        adj[hist[i]].erase(hist[(i+1)%hist.size()]);
        adj[hist[(i+1)%hist.size()]].erase(hist[i]);
      }
    }
  }

  // cout << ans.size() << endl;
  for (auto v : ans) {
    // cout << v.size() << " ";
    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:47:25: 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]
   47 |       for (int i = 0; i < hist.size(); i++) {
      |                       ~~^~~~~~~~~~~~~

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