Submission #979154

#	Time	Username	Problem	Language	Result	Execution time	Memory
979154		Sharky	Senior Postmen (BOI14_postmen)	C++17	100 / 100	359 ms	92664 KiB

postmen

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

const int N = 500005;
bool seen[N];
vector<pair<int, int>> adj[N];
vector<int> path;
vector<vector<int>> ans;
int occ[N];

void dfs(int node) {
    while (!adj[node].empty()) {
        auto [son, idx] = adj[node].back();
        adj[node].pop_back();
        if (seen[idx]) continue;
        seen[idx] = true;
        dfs(son);
    }
    if (occ[node] != -1) {
        int idx = occ[node];
        vector<int> tmp;
        while (path.size() >= idx + 1) {
            tmp.push_back(path.back());
            occ[path.back()] = -1;
            path.pop_back();
        }
        reverse(tmp.begin(), tmp.end());
        ans.push_back(tmp);
    }
    occ[node] = path.size();
    path.push_back(node);
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    for (int i = 1; i <= n; i++) occ[i] = -1;
    for (int i = 1; i <= n; i++) {
        while (!adj[i].empty()) dfs(i);
        if (path.size() > 1) ans.push_back(path); 
        path.clear();
    }
    for (auto& path : ans) {
        for (auto& e : path) cout << e << ' ';
        cout << '\n';
    }
}

Compilation message (stderr)

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:22:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |         while (path.size() >= idx + 1) {
      |                ~~~~~~~~~~~~^~~~~~~~~~

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