Персистентное ДО на кучу операций

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define long ll
#define all(x) begin(x), end(x)

const int M1  = 1e9 + 7;
const int M2  = 1e9 + 33;
const int MAX = 1e7 + 7;
const int N   = 1e5 + 5;

int pow1[N + 1], pow2[N + 1];

struct Node {
    Node *l, *r;
    int h1, h2;
    bool zero;
    Node() :
        l(nullptr),
        r(nullptr),
        h1(0),
        h2(0),
        zero(false) {}
};

bool check_full(Node *t, int len) {
    assert(t);
    return t->h1 == (pow1[len] + M1 - 1) % M1 && t->h2 == (pow2[len] + M2 - 1) % M2;
}

Node pool[MAX];
int pool_ptr = 0;

__attribute__((warn_unused_result))
Node *make_node() {
    return pool + pool_ptr++;
}

__attribute__((warn_unused_result))
Node *clone_node(Node *v) {
    assert(v);
    Node *res   = make_node();
    res->l      = v->l;
    res->r      = v->r;
    res->h1     = v->h1;
    res->h2     = v->h2;
    res->zero   = v->zero;
    return res;
}

void push(Node *t) {
    if (t->zero) {
        if (!t->l) {
            t->l = make_node();
        }
        t->l->zero = true;
        t->l->h1   = 0;
        t->l->h2   = 0;
        if (!t->r) {
            t->r = make_node();
        }
        t->r->zero = true;
        t->r->h1   = 0;
        t->r->h2   = 0;
    }
    t->zero = false;
}

__attribute__((warn_unused_result))
Node *pull(Node *t, int l, int r) {
    assert(l && r);
    long l1 = 0, r1 = 0, l2 = 0, r2 = 0;
    if (t->l) {
        l1 = t->l->h1;
        l2 = t->l->h2;
    }
    if (t->r) {
        r1 = t->r->h1;
        r2 = t->r->h2;
    }
    t->h1 = (int)((l1 + r1 * pow1[l]) % M1);
    t->h2 = (int)((l2 + r2 * pow2[l]) % M2);
    return t;
}

__attribute__((warn_unused_result))
Node *zero_range(Node *t, int vl, int vr, int ql, int qr) {
    if (qr <= vl || vr <= ql || !t) {
        return t;
    }
    t = clone_node(t);
    if (ql <= vl && vr <= qr) {
        t->zero = true;
        t->h1   = 0;
        t->h2   = 0;
        return t;
    }
    int vm = (vl + vr) / 2;
    push(t);
    t->l = zero_range(t->l, vl, vm, ql, qr);
    t->r = zero_range(t->r, vm, vr, ql, qr);
    return pull(t, vm - vl, vr - vm);
}

__attribute__((warn_unused_result))
Node *one_point(Node *t, int vl, int vr, int qp) {
    assert(vl <= qp && qp < vr);
    if (!t) {
        t = make_node();
    } else {
        t = clone_node(t);
    }
    if (vr - vl == 1) {
        t->h1 = 1;
        t->h2 = 1;
        return t;
    }
    int vm = (vl + vr) / 2;
    push(t);
    if (qp < vm) {
        t->l = one_point(t->l, vl, vm, qp);
    } else {
        t->r = one_point(t->r, vm, vr, qp);
    }
    return pull(t, vm - vl, vr - vm);
}

__attribute__((warn_unused_result))
pair<int, Node *> find_first_zero(Node *t, int vl, int vr, int ql) {
    if (vr <= ql) {
        return {-1, t};
    }
    if (!t) {
        return {max(vl, ql), t};
    }
    if (check_full(t, vr - vl)) {
        return {-1, t};
    }
    if (vr - vl == 1 && t->h1 == 0 && t->h2 == 0) {
        return {vl, t};
    }
    t = clone_node(t);
    int vm = (vl + vr) / 2;
    push(t);
    int answer;
    tie(answer, t->l) = find_first_zero(t->l, vl, vm, ql);
    if (answer != -1) {
        return { answer, t };
    }
    tie(answer, t->r) = find_first_zero(t->r, vm, vr, ql);
    return { answer, t };
}

__attribute__((warn_unused_result))
tuple<int, Node *, Node *> lcp(Node *a, Node *b, int vl, int vr) {
    pair<int, int> hash_a(0, 0);
    pair<int, int> hash_b(0, 0);
    if (a) {
        hash_a = make_pair(a->h1, a->h2);
    }
    if (b) {
        hash_b = make_pair(b->h1, b->h2);
    }

    if (hash_a == hash_b) {
        return make_tuple(vr - vl, a, b);
    }
    if (vr - vl == 1) {
        return make_tuple(0, a, b);
    }
    if (!a) {
        a = make_node();
    } else {
        a = clone_node(a);
    }
    if (!b) {
        b = make_node();
    } else {
        b = clone_node(b);
    }
    int vm = (vl + vr) / 2;
    int answer;
    push(a);
    push(b);
    tie(answer, a->r, b->r) = lcp(a->r, b->r, vm, vr);
    if (answer == vr - vm) {
        tie(answer, a->l, b->l) = lcp(a->l, b->l, vl, vm);
        return make_tuple(vr - vm + answer, a, b);
    }
    return make_tuple(answer, a, b);
}

__attribute__((warn_unused_result))
pair<int, Node *> get_value(Node *t, int vl, int vr, int qp) {
    assert(vl <= qp && qp < vr);
    if (!t) {
        return { 0, t };
    }
    if (vr - vl == 1) {
        return { t->h1, t };
    }
    t = clone_node(t);
    int vm = (vl + vr) / 2;
    push(t);
    int answer;
    if (qp < vm) {
        tie(answer, t->l) = get_value(t->l, vl, vm, qp);
        return { answer, t };
    } else {
        tie(answer, t->r) = get_value(t->r, vm, vr, qp);
        return { answer, t };
    }
}

__attribute__((warn_unused_result))
Node *print(Node *t, int vl, int vr, int lim) {
    if (vr - vl == 1) {
        if (lim > 0) {
            cout << (t && t->h1);
        }
        return t;
    }
    if (t) {
        t = clone_node(t);
        push(t);
        int vm = (vl + vr) / 2;
        t->r = print(t->r, vm, vr, lim - (vm - vl));
        t->l = print(t->l, vl, vm, lim);
    } else {
        for (int i = vl; i < min(vr, vl + lim); ++i) {
            cout << '0';
        }
    }
    return t;
}

void print(Node *&num, int lim) {
    if (num) {
        num = print(num, 0, N, lim);
    } else {
        while (lim--) {
            cout << '0';
        }
    }
    cout << endl;
}

__attribute__((warn_unused_result))
Node *add_power(Node *num, int p) {
    int x;
    tie(x, num) = find_first_zero(num, 0, N, p);
    num = zero_range(num, 0, N, p, x);
    num = one_point(num, 0, N, x);
    return num;
}

int get_mod(Node *t) {
    if (t) {
        return t->h1;
    }
    return 0;
}

int compare(Node *&a, Node *&b) {
    int l;
    tie(l, a, b) = lcp(a, b, 0, N);
    if (l == N) {
        return 0;
    }
    l = N - l - 1;
    int x, y;
    tie(x, a) = get_value(a, 0, N, l);
    tie(y, b) = get_value(b, 0, N, l);
    if (x < y) {
        return -1;
    } else {
        return +1;
    }
}
bool cmp(Node *&a, Node *&b) {
    return compare(a, b) == -1;
}
bool operator<(pair<Node *, int> &a, pair<Node *, int> &b) {
    int res = compare(a.first, b.first);
    if (res == 0) {
        return a.second < b.second;
    }
    return res == -1;
}

const int MOD   = 1e9 + 7;
int n, m;

vector<pair<int, int>> g[N];
Node *node_dist[N];
int dist[N];
int anc[N];


int main() {
#ifdef LC
    //assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    pow1[0] = 1;
    pow2[0] = 1;
    for (int i = 1; i <= N; ++i) {
        pow1[i] = (pow1[i - 1] * 2) % M1;
        pow2[i] = (pow2[i - 1] * 2) % M2;
    }

    cin >> n >> m;
    for (int a, b, x, i = 0; i < m; ++i) {
        cin >> a >> b >> x;
        --a;
        --b;
        g[a].emplace_back(b, x);
        g[b].emplace_back(a, x);
    }
    int start, finish;
    cin >> start >> finish;
    --start;
    --finish;

    fill_n(dist, N, -1);
    fill_n(anc, N, -1);
    dist[start] = 0;

    set<pair<Node *, int>> q;

    q.emplace(nullptr, start);

    while (q.size()) {
        pair<Node *, int> d_v = *q.begin();
        Node *d;
        if (d_v.first) {
            d = clone_node(d_v.first);
        } else {
            d = make_node();
        }
        int v = d_v.second;
        //cerr << "POP " << v + 1 << '\t';
        //print(node_dist[v], 10);
        //print(d, 10);

        q.erase(q.begin());
        dist[v] = get_mod(d);
        for (const auto &u_x : g[v]) {
            Node *possible = add_power(d, u_x.second);
            assert(possible);
            if (dist[u_x.first] == -1 || compare(possible, node_dist[u_x.first]) == -1) {
                anc[u_x.first] = v;
                q.erase({ node_dist[u_x.first], u_x.first });
                node_dist[u_x.first] = clone_node(possible);
                dist[u_x.first] = 0;
                q.emplace(node_dist[u_x.first], u_x.first);
            }
        }
    }

    cout << dist[finish] << '\n';
    if (dist[finish] != -1) {
        vector<int> path;
        int v = finish;
        while (v != -1) {
            path.push_back(v);
            v = anc[v];
        }
        cout << (int)path.size() << '\n';
        reverse(all(path));
        for (int e : path) {
            cout << e + 1 << ' ';
        }
        cout << '\n';
    }
    /*cin >> n;
    vector<Node *> arr(n);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        Node *num = nullptr;
        while (x >= 0) {
            num = add_power(num, x);
            cin >> x;
        }
        arr[i] = num;
    }

    sort(all(arr), cmp);

    for (int i = 0; i < n; ++i) {
        cout << get_mod(arr[i]) << '\t';
        print(arr[i], 50);
    }*/

    return 0;
}

/*
3
0 0 0 0 0 0 0 -1
1 1 1 -1
2 -1
*/

/*
9
100 -1
0 -1
0 0 0 0 -1
0 0 -1
0 0 0 -1
1 -1
2 -1
20 20 -1
10 -1
* */