Submission #1116450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116450		gustavo_d	Senior Postmen (BOI14_postmen)	C++17	100 / 100	343 ms	80056 KiB

postmen

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

#pragma GCC optmize("O3")

const int MAXN = 5e5;

struct Edge {
    int v, id;
    Edge(int _v=0, int _id=0): v(_v), id(_id) {}
};
vector<Edge> adj[MAXN];
bool mark[MAXN];
bool in_eulerian[MAXN];
vector<int> eulerian;

void dfs(int v) {
    while (!adj[v].empty()) {
        Edge ed = adj[v].back();
        adj[v].pop_back();
        if (mark[ed.id]) continue;
        mark[ed.id] = true;
        dfs(ed.v);
    }
    if (in_eulerian[v]) {
        int i = -1;
        while (i != v) {
            i = eulerian.back();
            eulerian.pop_back();
            in_eulerian[i] = false;
            cout << i+1 << ' ';
        }
        cout << '\n';
    }
    in_eulerian[v] = true;
    eulerian.push_back(v);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, m; cin >> n >> m;
    for (int i=0; i<m; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(Edge(v, i));
        adj[v].push_back(Edge(u, i));
    }
    for (int i=0; i<n; i++) {
        if (!adj[i].empty()) dfs(i);
    }

    return 0;
}

Compilation message (stderr)

postmen.cpp:4: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    4 | #pragma GCC optmize("O3")
      |

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