結果

問題 No.772 Dynamic Distance Sum
ユーザー yosupotyosupot
提出日時 2018-12-15 15:32:43
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 7,318 bytes
コンパイル時間 3,065 ms
コンパイル使用メモリ 227,632 KB
実行使用メモリ 814,656 KB
最終ジャッジ日時 2023-10-26 00:13:12
合計ジャッジ時間 5,937 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

struct TTNode {
    using NP = TTNode*;

    bool rev = false;
    array<array<NP, 2>, 2> ch = {}; //tree, light-tree
    NP p = nullptr, lt = nullptr;

    struct D {
        ll cnt = 0, pd = 0, upd = 0, dwd = 0;
        // l is parent of r
        static D merge_h(const D& l, const D& r) {
            return {l.cnt + r.cnt, l.pd + r.pd, l.upd + r.upd + l.pd * r.cnt, l.dwd + r.dwd + r.pd * l.cnt};
        }
        // l and r is parallel
        static D merge_w(const D& l, const D& r) {
            // TODO: tukai nikui...
            return {l.cnt + r.cnt, 0, l.upd + r.upd, 0};
        }
        // add parent for r(subtrees)
        static D join(const D& l, const D& r) {
            assert(l.upd == l.dwd);
            return {l.cnt + r.cnt, l.pd, l.upd + r.upd + l.pd * r.cnt, l.dwd + r.upd + l.pd * r.cnt};
        }
        static D rev(const D& l) {
            return D{l.cnt, l.pd, l.dwd, l.upd};
        }
    };
    D single = D(), subtree = D(), subtrees = D();

    NP search(ll nw, ll f) {
        //search heavy
        assert(subtree.cnt >= nw);
        push();
        if (ch[0][1] && ch[0][1]->subtree.cnt >= nw) return ch[0][1]->search(nw, f);
        if (ch[0][1]) nw -= ch[0][1]->subtree.cnt;
        if (single.cnt + (lt ? lt->subtrees.cnt : 0) >= nw) {
            if (!lt || lt->subtrees.cnt < f) return this;
            auto q = lt->search_light(f);
            if (!q) return this;
            return q;
        }
        nw -= single.cnt;
        if (lt) nw -= lt->subtrees.cnt;
        assert(ch[0][0]);
        return ch[0][0]->search(nw, f);
    }
    NP search_light(ll f) {
        assert(subtrees.cnt >= f);
        if (subtree.cnt >= f) {
            return search(f, f);
        }
        push();
        if (ch[1][0] && ch[1][0]->subtrees.cnt >= f) return ch[1][0]->search_light(f);
        if (ch[1][1] && ch[1][1]->subtrees.cnt >= f) return ch[1][1]->search_light(f);
        expose();
        return nullptr;
    }
    void init_node(ll cnt, ll d) {
        single.cnt = cnt;
        single.pd = d;
        single.upd = single.dwd = cnt * d;
        update();
    }
    void update_subs() {
        subtrees = subtree;
        if (ch[1][0]) subtrees = D::merge_w(ch[1][0]->subtrees, subtrees);
        if (ch[1][1]) subtrees = D::merge_w(subtrees, ch[1][1]->subtrees);
    }
    void update() {
        assert(!rev);
        subtree = single;
        if (lt) subtree = D::join(single, lt->subtrees);
        if (ch[0][0]) subtree = D::merge_h(ch[0][0]->subtree, subtree);
        if (ch[0][1]) subtree = D::merge_h(subtree, ch[0][1]->subtree);
        update_subs();
    }
    void revdata() {
        rev ^= true; swap(ch[0][0], ch[0][1]); // Important
        subtree = D::rev(subtree);
        update_subs();
    }
    void push() {
        if (rev) {
            if (ch[0][0]) ch[0][0]->revdata();
            if (ch[0][1]) ch[0][1]->revdata();
            rev = false;
        }
    }
    //optimize? : template<int ty>
    int pos(int ty) {
        if (p) {
            if (p->ch[ty][0] == this) return 0;
            if (p->ch[ty][1] == this) return 1;
        }
        return -1;
    }
    static void con(NP p, NP& cp, NP ch) { cp = ch; if (ch) ch->p = p; }
    void rot(int ty) {
        int ps = pos(ty);
        NP _p = p, q = p->p;
        if (ty == 0) {
            ch[1] = _p->ch[1]; _p->ch[1].fill(nullptr);
            for (auto& x: ch[1]) if (x) x->p = this;
        }
        con(_p, _p->ch[ty][ps], ch[ty][1-ps]);
        con(this, ch[ty][1-ps], _p);
        _p->update(); update();
        p = q;
        if (!q) return;
        if (q->lt == _p) q->lt = this;
        for (auto& v: q->ch) for (auto& x: v) if (x == _p) x = this;
        q->update();
    }
    void splay(int ty) {
        int ps;
        while ((ps = pos(ty)) != -1) {
            int pps = p->pos(ty);
            if (pps == -1) {
                rot(ty);
            } else if (ps == pps) {
                p->rot(ty); rot(ty);
            } else {
                rot(ty); rot(ty);
            }
        }
    }
    void expose() {
        supush();
        splay(0); splay(1);
        if (NP z = ch[0][1]) {
            z->push();
            con(z, z->ch[1][1], lt);
            lt = z; ch[0][1] = nullptr;
            z->update(); update();
        }
        NP u = p;
        while (u) {
            u->splay(0); u->splay(1);
            NP ur = u->lt;
            if (auto r = u->ch[0][1]) {
                // swap ur, r
                r->push();
                r->ch[1] = ur->ch[1]; ur->ch[1].fill(nullptr);
                for (auto& x: r->ch[1]) if (x) x->p = r;
                r->update();
                u->lt = r;
            } else if (!ur->ch[1][0]) {
                // use ur->ch[1][1]
                con(u, u->lt, ur->ch[1][1]);
            } else {
                // use prev(ur) in light-tree
                NP q = ur->ch[1][0];
                con(u, u->lt, q);
                q->push();
                while (q->ch[1][1]) {
                    q = q->ch[1][1]; q->push();
                }
                q->splay(1);
                con(q, q->ch[1][1], ur->ch[1][1]); q->update();
            }
            ur->ch[1].fill(nullptr); ur->update();
            u->ch[0][1] = ur; u->update();
            u = u->p;
        }
        splay(0);
    }
    void supush() {
        if (p) p->supush();
        push();
    }
    void link(NP r) {
        evert(); r->expose();
        assert(!r->ch[0][1]);
        con(r, r->ch[0][1], this);
        r->update();
    }
    void cut() {
        expose();
        ch[0][0]->p = nullptr; ch[0][0] = nullptr;
        update();
    }
    void evert() {
        expose();
        revdata();
        expose();
    }
};

const int MN = 100500;
const int MQ = 300500;
TTNode vtr[MN + MQ];

int main() {
    ios::sync_with_stdio(false); // Warning!!!!!
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        vtr[i].init_node(1, 0);
    }
    using P = pair<int, int>;
    map<P, int> mp;
    for (int ph = 0; ph < q; ph++) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int a, b; ll c;
            cin >> a >> b >> c; a--; b--;
            if (a > b) swap(a, b);
            mp[P(a, b)] = ph;
            vtr[n + ph].init_node(0, c);
            vtr[a].evert();
            vtr[a].link(vtr + n + ph);
            vtr[n + ph].link(vtr + b);
        } else if (ty == 2) {
            int a, b;
            cin >> a >> b; a--; b--;
            if (a > b) swap(a, b);
            int c = mp[P(a, b)];
            vtr[a].evert();
            vtr[n + c].cut();
            vtr[b].cut();
        } else if (ty == 3) {
            int a;
            cin >> a; a--;
            vtr[a].evert();
            vtr[a].init_node(1 - vtr[a].single.cnt, 0);
            int z = (vtr[a].subtree.cnt + 1) / 2;
            auto p = vtr[a].search(z, z);
            p->evert();
            cout << p->subtree.upd << "\n";
        } else {
            assert(false);
        }
    }
    return 0;
}
0