Submission #412796

#	Time	Username	Problem	Language	Result	Execution time	Memory
412796		fvogel499	Senior Postmen (BOI14_postmen)	C++14	55 / 100	531 ms	68580 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 pib pair<int, *obj>
#define f first
#define s second

#define pb push_back
#define ins insert

#define int ll
#define ll long long

int encode(int a, int b) { return (min(a, b)*1000000+max(a, b)); }

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

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

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

    unordered_set<int> usedEdges;
    vector<int> circuit;
    vector<int> path;
    path.pb(0);
    while (!path.empty()) {
        while (!graph[path.back()].empty() and usedEdges.find(encode(path.back(), graph[path.back()].back())) != usedEdges.end()) graph[path.back()].pop_back();
        if (graph[path.back()].empty()) {
            circuit.pb(path.back());
            path.pop_back();
        }
        else {
            int nn = graph[path.back()].back();
            graph[path.back()].pop_back();
            usedEdges.insert(encode(path.back(), nn));
            path.pb(nn);
        }
    }

    bool as [n];
    memset(as, false, n);
    vector<int> st;
    for (int i : circuit) {
        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);
    }

    int d = 0;
    d++;
}

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