cplib-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: data_structure/test/link_cut_tree.noncommutative2.stress.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" // DUMMY
#include "../link_cut_tree.hpp"
#include "../../random/xorshift.hpp"

#include <algorithm>
#include <cassert>
#include <iostream>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

struct S {
    int sz, sum, lhi, rhi, inhi;
    S() = default;
    S(int x) : sz(1), sum(x), lhi(x), rhi(x), inhi(x) {}
    S(int sz_, int sum_, int lhi_, int rhi_, int inhi_)
        : sz(sz_), sum(sum_), lhi(lhi_), rhi(rhi_), inhi(inhi_) {}
    bool operator==(const S &x) const {
        return sz == x.sz and sum == x.sum and lhi == x.lhi and rhi == x.rhi and inhi == x.inhi;
    }
    template <class OStream> friend OStream &operator<<(OStream &os, const S &x) {
        return os << '[' << x.sz << ',' << x.sum << ',' << x.lhi << ',' << x.rhi << ',' << x.inhi
                  << ']';
    }
};
using F = pair<bool, int>;
S op(S l, S r) {
    return S(l.sz + r.sz, l.sum + r.sum, max(l.sum + r.lhi, l.lhi), max(l.rhi + r.sum, r.rhi),
             max({l.inhi, r.inhi, l.rhi + r.lhi}));
}
S reversal(S x) { return S(x.sz, x.sum, x.rhi, x.lhi, x.inhi); }
S mapping(F f, S x) {
    if (f.first) {
        auto v = f.second;
        auto sum = x.sz * v;
        return S{x.sz, sum, max(v, sum), max(v, sum), max(v, sum)};
    } else {
        return x;
    }
}
F composition(F fnew, F gold) { return fnew.first ? fnew : gold; }
F id() { return {false, 0}; }
using LCT = lazy_linkcuttree<S, F, op, reversal, mapping, composition, id>;

const int NTRY = 1000;
const int VMAX = 20;
const int QPERTRY = 10000;
const int AMAX = 20;

vector<int> connected_vertices(int N, int r, const vector<unordered_set<int>> &to) {
    vector<int> visited(N);
    vector<int> ret, tmp{r};
    while (tmp.size()) {
        int now = tmp.back();
        tmp.pop_back();
        ret.push_back(now);
        visited[now] = 1;
        for (auto nxt : to[now]) {
            if (!visited[nxt]) tmp.push_back(nxt);
        }
    }
    return ret;
}

vector<int> get_rev_path(int s, int t, int prv, const vector<unordered_set<int>> &to) {
    if (s == t) return {s};
    for (auto nxt : to[s]) {
        if (nxt == prv) continue;
        auto v = get_rev_path(nxt, t, s, to);
        if (v.size()) {
            v.push_back(s);
            return v;
        }
    }
    return {};
}

int gen_rand_a() { return rand_int() % (AMAX * 2 + 1) - AMAX; }

int main() {
    for (int ntry = 0; ntry < NTRY; ntry++) {
        const int N = 2 + rand_int() % (VMAX - 1);
        vector<S> A(N);
        LCT tree;
        vector<LCT::Node *> nodes;

        for (int i = 0; i < N; i++) {
            A[i] = gen_rand_a();
            nodes.push_back(tree.make_node(A[i]));
        }
        vector<pair<int, int>> edges;
        vector<unordered_set<int>> to(N);

        auto try_to_add_edge = [&]() {
            int a = rand_int() % N;
            vector<int> is_cmp(N, 1);
            for (auto i : connected_vertices(N, a, to)) is_cmp[i] = 0;
            vector<int> cmp;
            for (int i = 0; i < N; i++) {
                if (is_cmp[i]) cmp.push_back(i);
            }
            if (cmp.empty()) return;
            int b = cmp[rand_int() % cmp.size()];

            edges.emplace_back(a, b);
            to[a].insert(b), to[b].insert(a);
            tree.link(nodes[a], nodes[b]);
        };

        for (int i = 0; i < N / 2; i++) try_to_add_edge();

        for (int q = 0; q < QPERTRY; q++) {
            const int tp = rand_int() % 6;
            if (tp == 0) {
                // cut() if possible
                if (edges.empty()) continue;
                int e = rand_int() % edges.size();
                int a = edges[e].first, b = edges[e].second;

                edges.erase(edges.begin() + e);
                to[a].erase(b), to[b].erase(a);
                tree.cut(nodes[a], nodes[b]);

            } else if (tp == 1) {
                // link() if possible
                try_to_add_edge();

            } else if (tp == 2) {
                // apply()
                const int u = rand_int() % N;
                auto conn = connected_vertices(N, u, to);
                int v = conn[rand_int() % conn.size()];
                const auto a = gen_rand_a();
                tree.apply(nodes[u], nodes[v], {true, a});

                for (auto i : get_rev_path(u, v, -1, to)) A[i] = a;

            } else if (tp == 3) {
                // prod()
                const int u = rand_int() % N;
                auto conn = connected_vertices(N, u, to);
                int v = conn[rand_int() % conn.size()];
                S ret1 = tree.prod(nodes[u], nodes[v]);

                auto ret2 = S(A[u]);
                for (auto i : get_rev_path(v, u, -1, to)) {
                    if (i != u) ret2 = op(ret2, A[i]);
                }
                assert(ret1 == ret2);

            } else if (tp == 4) {
                // set()
                const int u = rand_int() % N;
                const auto a = gen_rand_a();
                tree.set(nodes[u], a);
                A[u] = a;

            } else if (tp == 5) {
                // get()
                const int u = rand_int() % N;
                const S a = tree.get(nodes[u]);
                assert(a == A[u]);
            } else {
                exit(8);
            }
        }
    }
    puts("Hello World");
}
#line 1 "data_structure/test/link_cut_tree.noncommutative2.stress.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" // DUMMY
#line 2 "data_structure/link_cut_tree.hpp"

// CUT begin
// Link-Cut Tree
// Reference:
// - https://www.slideshare.net/iwiwi/2-12188845
// - https://ei1333.github.io/library/structure/lct/link-cut-tree-lazy-path.cpp
template <class S, class F, S (*op)(S, S), S (*reversal)(S), S (*mapping)(F, S),
          F (*composition)(F, F), F (*id)()>
class lazy_linkcuttree {
public:
    struct Node {
        Node *l, *r, *p;
        S d, sum;
        F lz;
        bool is_reversed;
        int sz;
        Node(S val)
            : l(nullptr), r(nullptr), p(nullptr), d(val), sum(val), lz(id()), is_reversed(false),
              sz(1) {}
        bool is_root() const { return !p || (p->l != this and p->r != this); }
        template <class OStream> friend OStream &operator<<(OStream &os, const Node &n) {
            os << '[';
            if (n.l) os << *(n.l) << ',';
            os << n.d << ',';
            if (n.r) os << *(n.r);
            return os << ']';
        }
    };

protected:
    void update(Node *t) {
        if (t == nullptr) return;
        t->sz = 1;
        t->sum = t->d;
        if (t->l) {
            t->sz += t->l->sz;
            t->sum = op(t->l->sum, t->sum);
        }
        if (t->r) {
            t->sz += t->r->sz;
            t->sum = op(t->sum, t->r->sum);
        }
    }
    void all_apply(Node *a, F b) {
        a->d = mapping(b, a->d);
        a->sum = mapping(b, a->sum);
        a->lz = composition(b, a->lz);
    }
    void _toggle(Node *t) {
        auto tmp = t->l;
        t->l = t->r, t->r = tmp;
        t->sum = reversal(t->sum);
        t->is_reversed ^= true;
    }

    void push(Node *&t) {
        if (t->lz != id()) {
            if (t->l) all_apply(t->l, t->lz);
            if (t->r) all_apply(t->r, t->lz);
            t->lz = id();
        }
        if (t->is_reversed) {
            if (t->l) _toggle(t->l);
            if (t->r) _toggle(t->r);
            t->is_reversed = false;
        }
    }

    void _rot_r(Node *t) {
        Node *x = t->p, *y = x->p;
        if ((x->l = t->r)) t->r->p = x;
        t->r = x, x->p = t;
        update(x), update(t);
        if ((t->p = y)) {
            if (y->l == x) y->l = t;
            if (y->r == x) y->r = t;
            update(y);
        }
    }
    void _rot_l(Node *t) {
        Node *x = t->p, *y = x->p;
        if ((x->r = t->l)) t->l->p = x;
        t->l = x, x->p = t;
        update(x), update(t);
        if ((t->p = y)) {
            if (y->l == x) y->l = t;
            if (y->r == x) y->r = t;
            update(y);
        }
    }

    void _splay(Node *t) {
        push(t);
        while (!t->is_root()) {
            Node *q = t->p;
            if (q->is_root()) {
                push(q), push(t);
                if (q->l == t)
                    _rot_r(t);
                else
                    _rot_l(t);
            } else {
                Node *r = q->p;
                push(r), push(q), push(t);
                if (r->l == q) {
                    if (q->l == t)
                        _rot_r(q), _rot_r(t);
                    else
                        _rot_l(t), _rot_r(t);
                } else {
                    if (q->r == t)
                        _rot_l(q), _rot_l(t);
                    else
                        _rot_r(t), _rot_l(t);
                }
            }
        }
    }

public:
    [[nodiscard]] Node *make_node(S val) { return new Node(val); }

    void evert(Node *t) { expose(t), _toggle(t), push(t); }

    Node *expose(Node *t) {
        Node *rp = nullptr;
        for (Node *cur = t; cur; cur = cur->p) {
            _splay(cur);
            cur->r = rp;
            update(cur);
            rp = cur;
        }
        _splay(t);
        return rp;
    }

    void link(Node *chi, Node *par) {
        evert(chi);
        expose(par);
        chi->p = par;
        par->r = chi;
        update(par);
    }

    void cut(Node *chi) {
        expose(chi);
        Node *par = chi->l;
        chi->l = nullptr;
        update(chi);
        par->p = nullptr;
    }

    void cut(Node *u, Node *v) { evert(u), cut(v); }

    Node *lca(Node *u, Node *v) { return expose(u), expose(v); }

    void set(Node *t, S x) { expose(t), t->d = x, update(t); }

    S get(Node *t) { return expose(t), t->d; }

    void apply(Node *u, Node *v, const F &x) {
        evert(u);
        expose(v);
        all_apply(v, x);
        push(v);
    }

    S prod(Node *u, Node *v) {
        evert(u);
        expose(v);
        return v->sum;
    }

    Node *kth_parent(Node *t, int k) {
        expose(t);
        while (t) {
            push(t);
            if (t->r and t->r->sz > k) {
                t = t->r;
            } else {
                if (t->r) k -= t->r->sz;
                if (k == 0) return t;
                k--;
                t = t->l;
            }
        }
        return nullptr;
    }

    bool is_connected(Node *u, Node *v) {
        expose(u), expose(v);
        return u == v or u->p;
    }
};
/* example usage:
struct S {
    int sz, sum, lhi, rhi, inhi;
    S(int x) : sz(1), sum(x), lhi(x), rhi(x), inhi(x) {}
    S(int sz_, int sum_, int lhi_, int rhi_, int inhi_)
        : sz(sz_), sum(sum_), lhi(lhi_), rhi(rhi_), inhi(inhi_) {}
};
using F = pair<bool, int>;
S op(S l, S r) {
    return S(l.sz + r.sz, l.sum + r.sum, max(l.sum + r.lhi, l.lhi), max(l.rhi + r.sum, r.rhi),
max<int>({l.inhi, r.inhi, l.rhi + r.lhi}));
}
S reversal(S x) { return S(x.sz, x.sum, x.rhi, x.lhi, x.inhi); }
S mapping(F f, S x) {
    if (f.first) {
        auto v = f.second;
        auto sum = x.sz * v;
        return S{x.sz, sum, max(v, sum), max(v, sum), max(v, sum)};
    } else {
        return x;
    }
}
F composition(F fnew, F gold) { return fnew.first ? fnew : gold; }
F id() { return {false, 0}; }
using LCT = lazy_linkcuttree<S, F, op, reversal, mapping, composition, id>;
vector<LCT::Node*> vs;
*/
#line 2 "random/xorshift.hpp"
#include <cstdint>

// CUT begin
uint32_t rand_int() // XorShift random integer generator
{
    static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    uint32_t t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
double rand_double() { return (double)rand_int() / UINT32_MAX; }
#line 4 "data_structure/test/link_cut_tree.noncommutative2.stress.test.cpp"

#include <algorithm>
#include <cassert>
#include <iostream>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

struct S {
    int sz, sum, lhi, rhi, inhi;
    S() = default;
    S(int x) : sz(1), sum(x), lhi(x), rhi(x), inhi(x) {}
    S(int sz_, int sum_, int lhi_, int rhi_, int inhi_)
        : sz(sz_), sum(sum_), lhi(lhi_), rhi(rhi_), inhi(inhi_) {}
    bool operator==(const S &x) const {
        return sz == x.sz and sum == x.sum and lhi == x.lhi and rhi == x.rhi and inhi == x.inhi;
    }
    template <class OStream> friend OStream &operator<<(OStream &os, const S &x) {
        return os << '[' << x.sz << ',' << x.sum << ',' << x.lhi << ',' << x.rhi << ',' << x.inhi
                  << ']';
    }
};
using F = pair<bool, int>;
S op(S l, S r) {
    return S(l.sz + r.sz, l.sum + r.sum, max(l.sum + r.lhi, l.lhi), max(l.rhi + r.sum, r.rhi),
             max({l.inhi, r.inhi, l.rhi + r.lhi}));
}
S reversal(S x) { return S(x.sz, x.sum, x.rhi, x.lhi, x.inhi); }
S mapping(F f, S x) {
    if (f.first) {
        auto v = f.second;
        auto sum = x.sz * v;
        return S{x.sz, sum, max(v, sum), max(v, sum), max(v, sum)};
    } else {
        return x;
    }
}
F composition(F fnew, F gold) { return fnew.first ? fnew : gold; }
F id() { return {false, 0}; }
using LCT = lazy_linkcuttree<S, F, op, reversal, mapping, composition, id>;

const int NTRY = 1000;
const int VMAX = 20;
const int QPERTRY = 10000;
const int AMAX = 20;

vector<int> connected_vertices(int N, int r, const vector<unordered_set<int>> &to) {
    vector<int> visited(N);
    vector<int> ret, tmp{r};
    while (tmp.size()) {
        int now = tmp.back();
        tmp.pop_back();
        ret.push_back(now);
        visited[now] = 1;
        for (auto nxt : to[now]) {
            if (!visited[nxt]) tmp.push_back(nxt);
        }
    }
    return ret;
}

vector<int> get_rev_path(int s, int t, int prv, const vector<unordered_set<int>> &to) {
    if (s == t) return {s};
    for (auto nxt : to[s]) {
        if (nxt == prv) continue;
        auto v = get_rev_path(nxt, t, s, to);
        if (v.size()) {
            v.push_back(s);
            return v;
        }
    }
    return {};
}

int gen_rand_a() { return rand_int() % (AMAX * 2 + 1) - AMAX; }

int main() {
    for (int ntry = 0; ntry < NTRY; ntry++) {
        const int N = 2 + rand_int() % (VMAX - 1);
        vector<S> A(N);
        LCT tree;
        vector<LCT::Node *> nodes;

        for (int i = 0; i < N; i++) {
            A[i] = gen_rand_a();
            nodes.push_back(tree.make_node(A[i]));
        }
        vector<pair<int, int>> edges;
        vector<unordered_set<int>> to(N);

        auto try_to_add_edge = [&]() {
            int a = rand_int() % N;
            vector<int> is_cmp(N, 1);
            for (auto i : connected_vertices(N, a, to)) is_cmp[i] = 0;
            vector<int> cmp;
            for (int i = 0; i < N; i++) {
                if (is_cmp[i]) cmp.push_back(i);
            }
            if (cmp.empty()) return;
            int b = cmp[rand_int() % cmp.size()];

            edges.emplace_back(a, b);
            to[a].insert(b), to[b].insert(a);
            tree.link(nodes[a], nodes[b]);
        };

        for (int i = 0; i < N / 2; i++) try_to_add_edge();

        for (int q = 0; q < QPERTRY; q++) {
            const int tp = rand_int() % 6;
            if (tp == 0) {
                // cut() if possible
                if (edges.empty()) continue;
                int e = rand_int() % edges.size();
                int a = edges[e].first, b = edges[e].second;

                edges.erase(edges.begin() + e);
                to[a].erase(b), to[b].erase(a);
                tree.cut(nodes[a], nodes[b]);

            } else if (tp == 1) {
                // link() if possible
                try_to_add_edge();

            } else if (tp == 2) {
                // apply()
                const int u = rand_int() % N;
                auto conn = connected_vertices(N, u, to);
                int v = conn[rand_int() % conn.size()];
                const auto a = gen_rand_a();
                tree.apply(nodes[u], nodes[v], {true, a});

                for (auto i : get_rev_path(u, v, -1, to)) A[i] = a;

            } else if (tp == 3) {
                // prod()
                const int u = rand_int() % N;
                auto conn = connected_vertices(N, u, to);
                int v = conn[rand_int() % conn.size()];
                S ret1 = tree.prod(nodes[u], nodes[v]);

                auto ret2 = S(A[u]);
                for (auto i : get_rev_path(v, u, -1, to)) {
                    if (i != u) ret2 = op(ret2, A[i]);
                }
                assert(ret1 == ret2);

            } else if (tp == 4) {
                // set()
                const int u = rand_int() % N;
                const auto a = gen_rand_a();
                tree.set(nodes[u], a);
                A[u] = a;

            } else if (tp == 5) {
                // get()
                const int u = rand_int() % N;
                const S a = tree.get(nodes[u]);
                assert(a == A[u]);
            } else {
                exit(8);
            }
        }
    }
    puts("Hello World");
}
Back to top page