Submission #412866

#	Time	Username	Problem	Language	Result	Execution time	Memory
412866		fvogel499	Senior Postmen (BOI14_postmen)	C++14	55 / 100	626 ms	39456 KiB

postmen

/*
File created on 05/27/2021 at 15:50:04.
Link to problem: https://oj.uz/problem/view/BOI14_postmen
Description: Hierholzer's algorithm for eulerian cycle + separation in "mini" cycles
Time complexity: O(N+M)
Space complexity: O(N+M)
Status: TLE
Copyright: Ⓒ 2021 Francois Vogel
*/

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

#define pb push_back
#define ins insert

#define ll long long

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, nbEdges;
    cin >> n >> nbEdges;

    vector<pii> graph [n];
    for (int i = 0; i < nbEdges; i++) {
        int nodeA, nodeB;
        cin >> nodeA >> nodeB;
        nodeA--;
        nodeB--;
        graph[nodeA].pb(pii(nodeB, i));
        graph[nodeB].pb(pii(nodeA, i));
    }

    bool usedEdge [nbEdges];
    memset(usedEdge, false, nbEdges);
    vector<int> circuit, path, st;
    bool as [n];
    memset(as, false, n);
    path.pb(0);
    while (!path.empty()) {
        while (!graph[path.back()].empty() and usedEdge[graph[path.back()].back().s]) graph[path.back()].pop_back();
        if (graph[path.back()].empty()) {
            circuit.pb(path.back());
            path.pop_back();
            int i = circuit.back();
            if (as[i]) {
                while (st.back() != i) {
                    as[st.back()] = false;
                    cout << st.back()+1 << " ";
                    st.pop_back();
                }
                st.pop_back();
                cout << i+1 << " " << endl;
            }
            as[i] = true;
            st.pb(i);
        }
        else {
            usedEdge[graph[path.back()].back().s] = true;
            int nn = graph[path.back()].back().f;
            graph[path.back()].pop_back();
            path.pb(nn);
        }
    }

    int d = 0;
    d++;
}

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