#998703 (C++17) No.772 Dynamic Distance Sum

提出ソース
結果

問題	No.772 Dynamic Distance Sum
ユーザー	dkim110807
提出日時	2024-07-31 22:21:01
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	18,881 bytes
コンパイル時間	3,086 ms
コンパイル使用メモリ	223,808 KB
実行使用メモリ	55,192 KB
最終ジャッジ日時	2024-07-31 22:21:19
合計ジャッジ時間	17,500 ms
ジャッジサーバーID （参考情報）	judge3 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	17 ms 53,392 KB
testcase_01	AC	17 ms 53,528 KB
testcase_02	AC	16 ms 53,524 KB
testcase_03	AC	16 ms 53,520 KB
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>

using ll = long long;

constexpr std::size_t MAX = 100'001;

struct Vertex {
    void *handle;
    int v;

    Vertex(int v = 0) : handle(nullptr), v(v) {}
};

struct Cluster {
    /*
     * chd   : count of nodes in boundary vertices
     * left  : sum of vertices from left
     * right : sum of vertices from right
     */
    ll len, weight, chd, ans, left, right;
    std::pair<ll, Vertex *> max;    // rake

    constexpr friend bool operator<(const std::pair<ll, Vertex *> &a, const std::pair<ll, Vertex *> &b) {
        return a.first < b.first;
    }

    Cluster(int len = 0) : len(len), weight(0), chd(0), ans(0), left(0), right(0) {}

    // swap boundary vertices
    void toggle() {
        std::swap(left, right);
    }

    // rake r to l
    static Cluster rake(const Cluster &l, const Cluster &r) {
        Cluster c;
        c.len = l.len;
        c.weight = l.weight, c.chd = l.chd + r.chd + r.weight;
        c.ans = l.right + r.right;
        c.left = l.left + r.left, c.right = l.right + r.right;
        c.max = std::max(l.max, r.max);
        return c;
    }

    static Cluster compress(const Cluster &l, Vertex *v, const Cluster &r) {
        Cluster c;
        c.len = l.len + r.len;
        c.weight = l.weight + l.chd + v->v + r.chd + r.weight;
        c.ans = l.right + r.left;
        c.left = l.left + r.left + (r.weight + l.chd + r.chd + v->v) * l.len;
        c.right = r.right + l.right + (l.weight + l.chd + r.chd + v->v) * r.len;
        c.max = {c.weight, v};
        return c;
    }
};

/*
 * Original code from https://beet-aizu.github.io/library/toptree/toptree.cpp
 * - edit (including annotation) : dkim110807
 */
template<std::size_t N = MAX>
struct TopTree {
    // each type of node can be compress, rake, edge (only if leaf node)
    enum Type {
        Compress, Rake, Edge
    };

    struct Node {
        Vertex *vs[2];      // boundary vertices
        Cluster dat;
        Node *p, *q;        // q is rake node (if exist)
        Node *ch[2];        // ch[0] : left / ch[1] : right
        bool rev, guard;
        Type type;

        Node() : p(nullptr), q(nullptr), rev(false), guard(false) {}
    };

    inline static std::array<Vertex, 2 * N> pool_vertex;
    inline static std::size_t ptr_vertex = 0;

    inline static std::array<Node, 4 * N> pool_node;
    inline static std::size_t ptr_node = 0;

    Cluster id;     // identity

    template<typename ...Args>
    inline Vertex *create(Args ...args) {
        auto t = &pool_vertex[ptr_vertex++];
        auto dummy = &pool_vertex[ptr_vertex++];
        *t = Vertex(std::forward<Args>(args)...);
        link(t, id, dummy);
        return t;
    }

    Node *recycle = nullptr;

    inline void dispose_node(Node *t) {
        t->p = recycle;
        recycle = t;
    }

    inline Node *get_new_node() {
        if (recycle) return new(std::exchange(recycle, recycle->p)) Node;
        return &(pool_node[ptr_node++]);
    }

    inline Node *edge(Vertex *u, Cluster w, Vertex *v) {
        auto t = get_new_node();
        t->vs[0] = u, t->vs[1] = v;
        t->dat = w;
        t->type = Type::Edge;
        return pushup(t);
    }

    inline Node *compress(Node *l, Node *r) {
        auto t = get_new_node();
        t->ch[0] = l, t->ch[1] = r;
        t->type = Type::Compress;
        return pushup(t);
    }

    inline Node *rake(Node *l, Node *r) {
        auto t = get_new_node();
        t->ch[0] = l, t->ch[1] = r;
        t->type = Type::Rake;
        return pushup(t);
    }

    int parent_dir(Node *t) {
        Node *p = t->p;
        if (!p || p->guard) return -1;  // if root or guard (when we meet guard nodes we stop splaying)
        if (p->ch[0] == t) return 0;    // if left node
        if (p->ch[1] == t) return 1;    // if right node
        return -1;
    }

    int parent_dir_ignore_guard(Node *t) {
        Node *p = t->p;
        if (!p) return -1;
        if (p->ch[0] == t) return 0;
        if (p->ch[1] == t) return 1;
        return -1;
    }

    // get data from child nodes
    inline Node *pushup(Node *const t) {
        Node *const l = t->ch[0];
        Node *const r = t->ch[1];

        if (t->type == Type::Compress) {
            assert(l->vs[1] == r->vs[0]);
            t->vs[0] = l->vs[0], t->vs[1] = r->vs[1];   // left node <-- compress --> right node

            Cluster lf = l->dat;
            if (t->q) { // if rake node exist
                assert(l->vs[1] == t->q->vs[1]);        // rake node must have same vertex
                lf = Cluster::rake(l->dat, t->q->dat);  // before compressing rake the cluster first
            }
            t->dat = Cluster::compress(lf, r->vs[0], r->dat);   // then compress

            l->vs[1]->handle = t;
        }

        if (t->type == Type::Rake) {
            propagate(t);
            assert(l->vs[1] == r->vs[1]);
            t->vs[0] = l->vs[0];
            t->vs[1] = l->vs[1];
            t->dat = Cluster::rake(l->dat, r->dat); // rake r to l
        } else {
            if (!t->p) {    // root cluster is handle for its boundary vertices
                t->vs[0]->handle = t;
                t->vs[1]->handle = t;
            } else if (t->p->type == Type::Compress) {
                if (parent_dir(t) == -1)
                    t->vs[0]->handle = t;
            } else if (t->p->type == Type::Rake) {
                t->vs[0]->handle = t;
            }
        }

        return t;
    }

    // reverse the boundary vertices
    inline void toggle(Node *t) {
        if (t->type == Type::Edge) {
            std::swap(t->vs[0], t->vs[1]);
            t->dat.toggle();
        } else if (t->type == Type::Compress) {
            std::swap(t->vs[0], t->vs[1]);
            t->dat.toggle();
            t->rev ^= true;     // lazy propagation
        } else if (t->type == Type::Rake) {
        } else std::abort();    // something wrong
    }

    inline void propagate(Node *t) {
        if (t->type == Type::Compress) {
            if (t->rev) {
                assert(t->ch[0] && t->ch[1]);
                std::swap(t->ch[0], t->ch[1]);
                toggle(t->ch[0]), toggle(t->ch[1]);
                t->rev = false;
            }
        }

        // Todo. lazy propagation here
    }

    void set_toggle(Node *v) {
        toggle(v);
        propagate(v);
    }

    void pushdown(Node *t) {
        if (!t) return;
        pushdown(t->p);
        propagate(t);
    }

    void rotate(Node *t, Node *x, std::size_t dir) {
        Node *y = x->p;
        int par = parent_dir_ignore_guard(x);
        propagate(t->ch[dir]);
        x->ch[dir ^ 1] = t->ch[dir];
        t->ch[dir]->p = x;
        t->ch[dir] = x;
        x->p = t;
        t->p = y;
        if (par != -1) y->ch[par] = t;
        else if (y && y->type == Type::Compress) y->q = t;
        pushup(x);
        pushup(t);
        if (y && !y->guard) pushup(y);
    }

    void splay(Node *t) {
        if (t->type == Type::Edge) return;
//        assert(t->type != Type::Edge);
        propagate(t);

        while (parent_dir(t) != -1) {
            Node *q = t->p;
            if (q->type != t->type) break;

            if (parent_dir(q) != -1 && q->p && q->p->type == q->type) {
                Node *r = q->p;
                if (r->p) propagate(r->p);
                propagate(r);
                propagate(q);
                propagate(t);
                int qt_dir = parent_dir(t), rq_dir = parent_dir(q);
                if (rq_dir == qt_dir) {
                    rotate(q, r, rq_dir ^ 1);
                    rotate(t, q, qt_dir ^ 1);
                } else {
                    rotate(t, q, qt_dir ^ 1);
                    rotate(t, r, rq_dir ^ 1);
                }
            } else {
                if (q->p) propagate(q->p);
                propagate(q);
                propagate(t);
                int qt_dir = parent_dir(t);
                rotate(t, q, qt_dir ^ 1);
            }
        }
    }

    // expose node to root cluster
    Node *expose(Node *t) {
        pushdown(t);

        while (true) {
            assert(t->type != Type::Rake);

            if (t->type == Type::Compress) splay(t);

            Node *n = nullptr;
            {
                Node *p = t->p;
                if (!p) break;
                if (p->type == Type::Rake) {
                    propagate(p);
                    splay(p);
                    n = p->p;
                }
                if (p->type == Type::Compress) {
                    propagate(p);
                    if (p->guard && parent_dir_ignore_guard(t) != -1) break;
                    n = p;
                }
            }
            splay(n);
            int dir = parent_dir_ignore_guard(n);
            if (dir == -1 || n->p->type == Type::Rake) dir = 0;

            Node *const c = n->ch[dir];
            if (dir == 1) {
                set_toggle(c);
                set_toggle(t);
            }
            int n_dir = parent_dir(t);
            if (n_dir != -1) {
                Node *const r = t->p;
                propagate(c);
                propagate(r);
                r->ch[n_dir] = c;
                c->p = r;
                n->ch[dir] = t;
                t->p = n;
                pushup(c);
                pushup(r);
                pushup(t);
                pushup(n);
                splay(r);
            } else {
                propagate(c);
                n->q = c;
                c->p = n;
                n->ch[dir] = t;
                t->p = n;
                pushup(c);
                pushup(t);
                pushup(n);
            }
            if (t->type == Type::Edge) t = n;
        }
        return t;
    }

    Node *expose(Vertex *v) {
        return expose((Node *) (v->handle));
    }

    // expose path u...v to root cluster
    void soft_expose(Vertex *u, Vertex *v) {
        pushdown((Node *) u->handle), pushdown((Node *) v->handle);
        Node *rt = expose(u);

        if (u->handle == v->handle) {
            if (rt->vs[1] == u || rt->vs[0] == v) set_toggle(rt);
            return;
        }

        rt->guard = true;
        Node *soft = expose(v);
        rt->guard = false;

        pushup(rt);
        if (parent_dir(soft) == 0) set_toggle(rt);
    }

    void bring(Node *rt) {
        Node *rk = rt->q;

        if (!rk) {
            Node *ll = rt->ch[0];
            dispose_node(ll->p);
            ll->p = nullptr;
            pushup(ll);
        } else if (rk->type == Type::Compress || rk->type == Type::Edge) {
            Node *nr = rk;
            set_toggle(nr);
            rt->ch[1] = nr;
            nr->p = rt;
            rt->q = nullptr;

            pushup(nr);
            pushup(rt);
        } else if (rk->type == Type::Rake) {
            propagate(rk);
            while (rk->ch[1]->type == Type::Rake) {
                propagate(rk->ch[1]);
                rk = rk->ch[1];
            }
            pushdown(rk);

            rt->guard = true;
            splay(rk);
            rt->guard = false;

            Node *ll = rk->ch[0];
            Node *rr = rk->ch[1];
            propagate(ll);
            set_toggle(rr);

            rt->ch[1] = rr;
            rr->p = rt;

            rt->q = ll;
            ll->p = rt;

            dispose_node(rk);
            pushup(ll);
            pushup(rr);
            pushup(rt);
        }
    }

    // link u-v with data w
    Node *link(Vertex *u, Cluster w, Vertex *v) {
        // single vertex doesn't have handle (so just link it)
        if (!u->handle && !v->handle) return edge(u, w, v);

        Node *nnu = (Node *) u->handle;
        Node *nnv = (Node *) v->handle;
        Node *ee = edge(u, w, v);
        Node *ll;

        assert(nnv);
        Node *vv = expose(nnv);
        propagate(vv);
        if (vv->vs[1] == v) set_toggle(vv);
        if (vv->vs[0] == v) {
            Node *nv = compress(ee, vv);
            ee->p = nv;
            pushup(ee);
            vv->p = nv;
            pushup(vv);
            pushup(nv);
            ll = nv;
        } else {
            Node *nv = vv;
            Node *ch = nv->ch[0];
            propagate(ch);
            nv->ch[0] = ee;
            ee->p = nv;
            pushup(ee);

            Node *bt = nv->q;
            Node *rk;
            if (bt) {
                propagate(bt);
                rk = rake(bt, ch);
                bt->p = rk;
                ch->p = rk;
                pushup(bt);
                pushup(ch);
            } else {
                rk = ch;
            }
            nv->q = rk;
            rk->p = nv;
            pushup(rk);
            pushup(nv);
            ll = nv;
        }

        assert(nnu);
        Node *uu = expose(nnu);
        propagate(uu);
        if (uu->vs[0] == u) set_toggle(uu);
        if (uu->vs[1] == u) {
            Node *tp = compress(uu, ll);
            uu->p = tp;
            ll->p = tp;
            pushup(uu);
            pushup(ll);
            pushup(tp);
        } else {
            Node *nu = uu;
            Node *ch = nu->ch[1];
            toggle(ch);
            propagate(ch);

            nu->ch[1] = ll;
            ll->p = nu;
            pushup(ll);

            Node *al = nu->q;
            Node *rk;
            if (al) {
                propagate(al);
                rk = rake(al, ch);
                al->p = rk;
                ch->p = rk;
                pushup(al);
                pushup(ch);
            } else {
                rk = ch;
            }
            nu->q = rk;
            rk->p = nu;
            pushup(rk);
            pushup(nu);
        }
        return ee;
    }

    // cut between u-v (it must exist)
    void cut(Vertex *u, Vertex *v) {
        soft_expose(u, v);
        Node *rt = (Node *) u->handle;
        propagate(rt);
        Node *rr = rt->ch[1];
        rr->p = nullptr;
        set_toggle(rr);
        assert(rr->ch[1]->type == Type::Edge);
        dispose_node(rr->ch[1]);
        bring(rr);
        bring(rt);
    }

    Node *path(Vertex *u, Vertex *v) {
        assert(u != v);
        soft_expose(u, v);
        Node *rt = (Node *) u->handle;
        splay(rt);
        propagate(rt);
        propagate(rt->ch[1]);
        propagate(rt->ch[1]->ch[0]);    // * propagate complete *
        return rt->ch[1]->ch[0];
    }

    void set_vertex(Vertex *u, Vertex v) {
        auto t = expose(u);
        // Todo.
        u->v = v.v;
        pushup(t);
    }

    // this must be edge - dkim110807
    void set_edge(Vertex *u, Vertex *v, const Cluster &w) {
        auto t = path(u, v);
        assert(t->type == Type::Edge);
        t->dat = w;
        while (t) pushup(t), t = t->p;
    }

    // Todo. lazy update here
    // If lazy is not required use set_edge
    void set_path(Vertex *u, Vertex *v, ll c) {
        Node *t = path(u, v);

    }

    Cluster get_path(Vertex *u, Vertex *v) {
        return path(u, v)->dat;
    }

    Cluster get_subtree(Vertex *v) {
        return expose(v)->dat;
    }

    // Todo. lazy update on subtree
    void set_subtree(Vertex *v) {
        Node *t = expose(v);

    }

    // subtree of v when root
    Cluster get_subtree(Vertex *root, Vertex *v) {
        if (root == v) return get_subtree(v);
        Node *t = path(root, v);
        Cluster res = t->p->ch[1]->dat;
        res.toggle();
        Node *rk = t->p->q;
        if (t->p->q) {
            assert(rk->vs[1] == t->p->ch[1]->vs[0]);
            res = Cluster::rake(res, rk->dat);
        }
        return res;
    }

    // I'm not sure with these things... maybe wrong (MST accepted)
    void set_root(Vertex *root) {
        expose(root);

        Node *r = (Node *) root->handle;

        while (r->p) r = r->p;

        expose(r);

        assert(!r->p);
    }

    Node *get_root(Vertex *v) {
        Node *n = (Node *) v->handle;
        assert(n != nullptr);
        while (n->p) n = n->p;
        splay(n);
        return n;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

    TopTree tree;

    int n, m;
    std::cin >> n >> m;

    std::vector<int> X(n + 1, 1);

    std::vector<Vertex *> node(n + 1);
    for (int i = 1; i <= n; i++) node[i] = tree.create(1);  // initially all $X_[v} = 1$

    /*
     * Non-local searching
     *
     * Center
     *  : Follow node having greater sum of weights or
     *  : Follow node having less max distance
     */
    auto center = [&](Vertex *v) -> Vertex * {
        using Node = decltype(tree)::Node;
        using Type = decltype(tree)::Type;

        Node *root = tree.expose(v);
        if (root->type == Type::Edge) return v;

        Node *c = root;
        ll left = 0, right = 0, sum = c->dat.weight;
        while (c->type == Type::Compress) {
            tree.propagate(c);

            Node *l = c->ch[0], *r = c->ch[1], *q = c->q;
            if ((l->dat.weight + left) * 2 > sum) {             // follow left
                right += c->dat.max.first - l->dat.weight;
                c = l;
            } else if ((r->dat.weight + right) * 2 > sum) {     // follow right
                left += c->dat.max.first - r->dat.weight;
                c = r;
            } else if (q && (q->dat.max.first * 2) > sum) {     // follow rake's max if rake exist
                /*
                 *                       c
                 *                     / | \
                 *                    /  |  \
                 *                   /   |   \
                 *                left   q   right
                 * follow 'q' -> every left become right
                 */
                right += left, left = 0;
                right += c->dat.max.first - q->dat.max.first;
                c = (Node *) q->dat.max.second->handle;
            } else {
                return c->dat.max.second;
            }
        }

        return nullptr;
    };

    ll last = 0;
    for (int op, a, b, c; m--;) {
        std::cin >> op;

        if (op == 1) {
            std::cin >> a >> b >> c;
            a = int((last + a - 1) % n + 1), b = int((last + b - 1) % n + 1);
            tree.link(node[a], c, node[b]);
        } else if (op == 2) {
            std::cin >> a >> b;
            a = int((last + a - 1) % n + 1), b = int((last + b - 1) % n + 1);
            tree.cut(node[a], node[b]);
        } else if (op == 3) {
            std::cin >> a;
            a = int((last + a - 1) % n + 1);
            X[a] = 1 - X[a];
            tree.set_vertex(node[a], X[a]);
            auto v = center(node[a]);
#ifdef LOCAL
            for (int i = 1; i <= n; i++) {
                if (v == node[i]) {
                    std::clog << "Center : " << i << "\n";
                    break;
                }
            }
#endif
            ll ans = tree.get_subtree(v).ans;
            std::cout << ans << "\n";
            last = (last + ans) % n;
        }
    }
}
yukicoder

結果

テストケース

ソースコード
