Submission #1354445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354445		mihai.25	Senior Postmen (BOI14_postmen)	C++20	100 / 100	167 ms	35308 KiB

postmen

#include <iostream>

#include <vector>

#include <stack>

using namespace std;

int n, m;

struct edge {

    int to, id;
};

vector<vector<edge>> adj;

vector<int> last_idx;

vector<bool> used_edge, in_stack;

void findCycles(int startNode) {

    stack<int> s;

    s.push(startNode);

    in_stack[startNode] = true;

    while (!s.empty()) {

        int u = s.top();

        bool found = false;

        while(last_idx[u] < adj[u].size()) {

            edge e = adj[u][last_idx[u]++];

            if (!used_edge[e.id]) {

                used_edge[e.id] = true;

                found = true;

                int v = e.to;

                if (in_stack[v]) {

                    printf("%d ", v);

                    while (s.top() != v) {

                        printf("%d ", s.top());

                        in_stack[s.top()] = false;

                        s.pop();
                    }

                    printf("\n");
                }
                else {

                    s.push(v);

                    in_stack[v] = true;
                }

                break;
            }
        }

        if (!found) {

            in_stack[u] = false;

            s.pop();
        }
    }
}

int main() {

    ios_base :: sync_with_stdio(false);

    cin.tie(nullptr);

    scanf("%d%d", &n, &m);

    adj.resize(n + 1);

    for (int i = 1; i <= m; ++i) {

        int u, v;

        scanf("%d%d", &u, &v);

        adj[u].push_back({v, i});

        adj[v].push_back({u, i});
    }

    last_idx.resize(n + 1);

    used_edge.resize(m + 1);

    in_stack.resize(n + 1);

    for (int i = 1; i <= n; ++i)
        findCycles(i);
    
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

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