Submission #1074862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074862		RauPro	Senior Postmen (BOI14_postmen)	C++17	100 / 100	410 ms	99528 KiB

postmen

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

#define MOD 1000000007
#define MAX_NODES 500010

vector<pair<int, int>> AL[MAX_NODES];
bool visited[MAX_NODES];
bool edge_visited[MAX_NODES];
int index_tracker[MAX_NODES];
int ans[MAX_NODES];

void print(const vector<int>& prt) {
    for (int i = 0; i < prt.size(); ++i) {
        if (i > 0) cout << " ";
        cout << prt[i];
    }
    cout << endl;
}

int dfs(int u, int size) {
    visited[u] = true;
    ans[size] = u;

    while (index_tracker[u] < AL[u].size()) {
        int v = AL[u][index_tracker[u]].first;
        int edge_index = AL[u][index_tracker[u]].second;
        index_tracker[u]++;

        if (edge_visited[edge_index]) {
            continue;
        }
        edge_visited[edge_index] = true;

        if (!visited[v]) {
            int returned_node = dfs(v, size + 1);
            if (returned_node == u) {
                continue;
            } else {
                visited[u] = false;
                return returned_node;
            }
        } else {
            vector<int> prt;
            for (int j = size; j >= 0; --j) {
                prt.push_back(ans[j]);
                if (ans[j] == v) {
                    break;
                }
            }
            print(prt);
            visited[u] = false;
            return v;
        }
    }
    return 0;
}

void solve() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        AL[u].emplace_back(v, i);
        AL[v].emplace_back(u, i);
        //cout << u << " " << v << " " << i << endl;
    }

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs(i, 0);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'void print(const std::vector<int>&)':
postmen.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < prt.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
postmen.cpp: In function 'int dfs(int, int)':
postmen.cpp:25:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     while (index_tracker[u] < AL[u].size()) {
      |            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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