Offcut - BIO 2022 Round 2

#include <bits/stdc++.h>

using namespace std;

/// Euler Path

const int MAX_E = 1<<19 + 1;

vector<vector<pair<int, int>>> g;
int edge[MAX_E][2];
bool usedE[MAX_E];
inline int getOther(int id, int v) {
    return v ^ edge[id][0] ^ edge[id][1];
}
vector<int> path; // of edges

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int r, c; cin >> r >> c;
    vector<vector<int>> grid(r, vector<int>(c));
    for (vector<int> &row : grid) {
        for (int &cell : row) cin >> cell;
    }

    /// Turn into graph on collectibles with offcuts being edges
    int n = r*c/4;
    g.resize(1+n);
    /// Cut it in any way - it will still be possible
    int nextOffcut = 1;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; j+=2) {
            int ii = i, jj = j, pairKey = nextOffcut<<1;
            if (j+1 < c) ++jj;
            else if (i % 2 == 0) ++ii, ++pairKey;
            else continue;
            ++nextOffcut;

            int x = grid[i][j], y = grid[ii][jj];
            // second value in pair indicates what to print - which is double the index of the offcut plus 1 if vertical
            g[x].emplace_back(y, pairKey);
            g[y].emplace_back(x, pairKey);
            edge[pairKey/2][0] = x, edge[pairKey/2][1] = y;
        }
    }

    vector<int> group[2];
    /// Distribute offcuts as alternating edges in euler path(s)
    int cuts = nextOffcut-1;
    for (int id = 1; id <= cuts; ++id) { // go through edges
        if (usedE[id]) continue;
        path.clear();
        // find euler path in this connected component
        // doing this with my own stack below since otherwise there is a segmentation fault on large test cases

        stack<pair<int, int>> st; // contains the node and edge
        st.emplace(edge[id][0], 0);
        while (!st.empty()) {
            int node = st.top().first;
            if (g[node].empty()) {
                if (st.top().second) path.push_back(st.top().second);
                st.pop();
            } else {
                int id = g[node].back().second;
                g[node].pop_back();
                if (usedE[id/2]) continue;
                usedE[id/2] = true;
                st.emplace(getOther(id/2, node), id);
            }
        }

        for (int i = 0; i < path.size(); ++i) {
            group[i&1].push_back(path[i]);
        }
    }

    /// Print the answer
    for (int gr = 0; gr <= 1; ++gr) {
        for (int key : group[gr]) {
            cout << (key>>1) << ((key&1) ? 'V' : 'H') << ' ';
        }
        cout << endl;
    }
    return 0;
}