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

提出ソース
結果

問題	No.772 Dynamic Distance Sum
ユーザー	tonegawa
提出日時	2024-09-09 10:02:51
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	862 ms / 5,000 ms
コード長	18,218 bytes
コンパイル時間	2,334 ms
コンパイル使用メモリ	178,288 KB
実行使用メモリ	76,460 KB
最終ジャッジ日時	2024-09-09 10:03:13
合計ジャッジ時間	21,140 ms
ジャッジサーバーID （参考情報）	judge1 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	3 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	6 ms 6,940 KB
testcase_05	AC	3 ms 6,944 KB
testcase_06	AC	4 ms 6,940 KB
testcase_07	AC	4 ms 6,944 KB
testcase_08	AC	4 ms 6,944 KB
testcase_09	AC	6 ms 6,944 KB
testcase_10	AC	5 ms 6,944 KB
testcase_11	AC	3 ms 6,940 KB
testcase_12	AC	832 ms 72,308 KB
testcase_13	AC	862 ms 73,096 KB
testcase_14	AC	735 ms 69,692 KB
testcase_15	AC	714 ms 68,992 KB
testcase_16	AC	847 ms 72,724 KB
testcase_17	AC	817 ms 72,596 KB
testcase_18	AC	605 ms 68,240 KB
testcase_19	AC	847 ms 76,460 KB
testcase_20	AC	561 ms 66,448 KB
testcase_21	AC	849 ms 75,136 KB
testcase_22	AC	840 ms 74,788 KB
testcase_23	AC	725 ms 74,424 KB
testcase_24	AC	748 ms 73,276 KB
testcase_25	AC	743 ms 75,080 KB
testcase_26	AC	794 ms 75,032 KB
testcase_27	AC	779 ms 72,544 KB
testcase_28	AC	796 ms 75,840 KB
testcase_29	AC	567 ms 70,740 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator << (std::ostream &dest, const std::pair<F, S> &p) {
    dest << p.first << ' ' << p.second;
    return dest;
}

template<typename A, typename B>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t);
    return dest;
}

template<typename A, typename B, typename C>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t);
    return dest;
}

template<typename A, typename B, typename C, typename D>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C, D> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t);
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<std::vector<T>> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz; i++) {
        int m = v[i].size();
        for (int j = 0; j < m; j++) dest << v[i][j] << (i != sz - 1 && j == m - 1 ? '\n' : ' ');
    }
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<T> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T, size_t sz>
std::ostream &operator << (std::ostream &dest, const std::array<T, sz> &v) {
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::set<T> &v) {
    for (auto itr = v.begin(); itr != v.end();) {
        dest << *itr;
        itr++;
        if (itr != v.end()) dest << ' ';
    }
    return dest;
}

template<typename T, typename E>
std::ostream &operator << (std::ostream &dest, const std::map<T, E> &v) {
    for (auto itr = v.begin(); itr != v.end(); ) {
        dest << '(' << itr->first << ", " << itr->second << ')';
        itr++;
        if (itr != v.end()) dest << '\n';
    }
    return dest;
}

template<typename T>
vector<T> make_vec(size_t sz, T val) { return std::vector<T>(sz, val); }

template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail) {
    return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}

template<typename T>
vector<T> read_vec(size_t sz) {
    std::vector<T> v(sz);
    for (int i = 0; i < (int)sz; i++) std::cin >> v[i];
    return v;
}

template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail) {
    auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
    for (int i = 0; i < (int)sz; i++) v[i] = read_vec<T>(tail...);
    return v;
}

// x / y以上の最小の整数
ll ceil_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? y - 1 : 0)) / y;
}

// x / y以下の最大の整数
ll floor_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? 0 : -y + 1)) / y;
}

void io_init() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
}



#include <unistd.h>

// サイズは空白や改行も含めた文字数
template<int size_in = 1 << 25, int size_out = 1 << 25>
struct fast_io {
    char ibuf[size_in], obuf[size_out];
    char *ip, *op;

    fast_io() : ip(ibuf), op(obuf) {
        int t = 0, k = 0;
        while ((k = read(STDIN_FILENO, ibuf + t, sizeof(ibuf) - t)) > 0) {
            t += k;
        }
    }
    
    ~fast_io() {
        int t = 0, k = 0;
        while ((k = write(STDOUT_FILENO, obuf + t, op - obuf - t)) > 0) {
            t += k;
        }
    }
  
    long long in() {
        long long x = 0;
        bool neg = false;
        for (; *ip < '+'; ip++) ;
        if (*ip == '-'){ neg = true; ip++;}
        else if (*ip == '+') ip++;
        for (; *ip >= '0'; ip++) x = 10 * x + *ip - '0';
        if (neg) x = -x;
        return x;
    }

    unsigned long long inu64() {
        unsigned long long x = 0;
        for (; *ip < '+'; ip++) ;
        if (*ip == '+') ip++;
        for (; *ip >= '0'; ip++) x = 10 * x + *ip - '0';
        return x;
    }

    char in_char() {
        for (; *ip < '!'; ip++) ;
        return *ip++;
    }
  
    void out(long long x, char c = 0) {
        static char tmp[20];
        if (!x) {
            *op++ = '0';
        } else {
            int i;
            if (x < 0) {
                *op++ = '-';
                x = -x;
            }
            for (i = 0; x; i++) {
                tmp[i] = x % 10;
                x /= 10;
            }
            for (i--; i >= 0; i--) *op++ = tmp[i] + '0';
        }
        if (c) *op++ = c;
    }

    void outu64(unsigned long long x, char c = 0) {
        static char tmp[20];
        if (!x) {
            *op++ = '0';
        } else {
            int i;
            for (i = 0; x; i++) {
                tmp[i] = x % 10;
                x /= 10;
            }
            for (i--; i >= 0; i--) *op++ = tmp[i] + '0';
        }
        if (c) *op++ = c;
    }

    void out_char(char x, char c = 0){
        *op++ = x;
        if (c) *op++ = c;
    }

    long long memory_size() {
        return (long long)(size_in + size_out) * sizeof(char);
    }
};





template<typename W>
struct centroid_dynamic {
    struct T { 
        W distsum, distsum_rev, w, wsum, len, lensum;
        T() : distsum(0), distsum_rev(0), w(0), wsum(0), len(0), lensum(0) {}
    };
    struct U {
        W distsum, wsum;
        U() : distsum(0), wsum(0) {}
    };
    struct node;
    struct node_in {
        node_in *lch, *rch, *par;
        W wmax;
        node *c, *wmaxnode;
        node_in(node *_self) : lch(nullptr), rch(nullptr), par(nullptr), wmax(_self->x.wsum), c(_self), wmaxnode(_self) {}
        bool is_root() { return !par; }
    };
    struct node {
        node *lch, *rch, *par;
        bool _flip;
        T x;
        U y;
        node_in *lic, *lip;
        node() : lch(nullptr), rch(nullptr), par(nullptr), _flip(false), x(), y(), lic(nullptr), lip(nullptr) {}
        bool is_root() { return !par || (par->lch != this && par->rch != this); }
    };

    // 重みwの頂点
    static node *make_node(W w) { 
        node *v = new node();
        v->x.w = v->x.wsum = w;
        return v;
    }

    // 長さlenの辺
    static node *make_edge(W len) {
        node *v = new node();
        v->x.len = v->x.lensum = len;
        return v;
    }

    static void update(node *v) {
        if (v->lch && v->lch->lip) std::swap(v->lip, v->lch->lip);
        if (v->rch && v->rch->lip) std::swap(v->lip, v->rch->lip);
        T lsum = (v->lch ? v->lch->x : T());
        T rsum = (v->rch ? v->rch->x : T());
        W a = lsum.distsum + lsum.lensum * v->x.w;
        W b = lsum.wsum + v->x.w;
        W c = lsum.lensum + v->x.len;
        W d = v->y.distsum + rsum.distsum;
        W e = v->y.wsum + rsum.wsum;
        v->x.distsum = a + d + c * e;
        v->x.distsum_rev = (rsum.distsum_rev + rsum.lensum * v->x.w) + (v->y.distsum + lsum.distsum_rev) + (rsum.lensum + v->x.len) * (v->y.wsum + lsum.wsum);
        v->x.wsum = b + e;
        v->x.lensum = c + rsum.lensum;
    }

    static void update(node_in *v) {
        v->wmax = v->c->x.wsum;
        v->wmaxnode = v->c;
        if (v->lch && v->wmax < v->lch->wmax) {
            v->wmax = v->lch->wmax;
            v->wmaxnode = v->lch->wmaxnode;
        }
        if (v->rch && v->wmax < v->rch->wmax) {
            v->wmax = v->rch->wmax;
            v->wmaxnode = v->rch->wmaxnode;
        }
    }

    static void push(node_in *v) {}

    static void flip(node *v) {
        v->_flip = !v->_flip;
        std::swap(v->x.distsum, v->x.distsum_rev);
        std::swap(v->lch, v->rch);
    }

    static void push(node *v) {
        if (v->_flip) {
            if (v->lch) flip(v->lch);
            if (v->rch) flip(v->rch);
            v->_flip = false;
        }
    }
    
    template<typename Node = node>
    static void splay(Node *v) {
        push(v);
        while (!v->is_root()) {
            Node *p = v->par;
            if (p->is_root()) {
                push(p), push(v);
                Node *pp = p->par;
                if(p->lch == v) {
                    if ((p->lch = v->rch)) p->lch->par = p;
                    update(p);
                    v->rch = p;
                    p->par = v;
                    update(v);
                } else {
                    if ((p->rch = v->lch)) p->rch->par = p;
                    update(p);
                    v->lch = p;
                    p->par = v;
                    update(v);
                }
                v->par = pp;
            } else {
                Node *pp = p->par;
                Node *ppp = pp->par;
                push(pp), push(p), push(v);
                if (pp->lch == p) {
                    if (p->lch == v) {
                        if ((pp->lch = p->rch)) pp->lch->par = pp;
                        update(pp);
                        p->rch = pp;
                        pp->par = p;
                        if ((p->lch = v->rch)) p->lch->par = p;
                        update(p);
                        v->rch = p;
                        p->par = v;
                        update(v);
                    } else {
                        if ((p->rch = v->lch)) p->rch->par = p;
                        update(p);
                        if ((pp->lch = v->rch)) pp->lch->par = pp;
                        update(pp);
                        v->lch = p;
                        v->rch = pp;
                        p->par = pp->par = v;
                        update(v);
                    }
                } else {
                    if(p->rch == v) {
                        if ((pp->rch = p->lch)) pp->rch->par = pp;
                        update(pp);
                        p->lch = pp;
                        pp->par = p;
                        if ((p->rch = v->lch)) p->rch->par = p;
                        update(p);
                        v->lch = p;
                        p->par = v;
                        update(v);
                    } else {
                        if ((p->lch = v->rch)) p->lch->par = p;
                        update(p);
                        if ((pp->rch = v->lch)) pp->rch->par = pp;
                        update(pp);
                        v->rch = p;
                        v->lch = pp;
                        p->par = pp->par = v;
                        update(v);
                    }
                }
                if ((v->par = ppp)) {
                    if (ppp->lch == pp) ppp->lch = v;
                    if (ppp->rch == pp) ppp->rch = v;
                }
            }
        }
        if constexpr (std::is_same<Node, node>::value == true) {
            if (v->lip) {
                v->lip->c = v;
            }
        }
    }
    
    static node* expose(node *v) {
        node *c = nullptr;
        for (node *u = v; u; u = u->par) {
            splay(u);
            node *r = u->rch;
            if (c) {
                u->y.distsum -= c->x.distsum;
                u->y.wsum -= c->x.wsum;
            }
            if (r) {
                u->y.distsum += r->x.distsum;
                u->y.wsum += r->x.wsum;
            }
            if (c && r) {
                node_in *p = c->lip;
                std::swap(c->lip, r->lip);
                p->c = r;
                update(p);
                splay<node_in>(p);
                u->lic = p;
            } else if (c) {
                node_in *p = c->lip;
                c->lip = nullptr;
                splay<node_in>(p);
                if (!p->lch || !p->rch) {
                    if (p->rch) std::swap(p->lch, p->rch);
                    if ((u->lic = p->lch)) p->lch->par = nullptr;
                } else {
                    node_in *L = p->lch, *R = p->rch;
                    R->par = nullptr;
                    while (R->lch) R = R->lch;
                    splay<node_in>(R);
                    R->lch = L;
                    L->par = R;
                    update(R);
                    u->lic = R;
                }
            } else if (r) {
                node_in *p = new node_in(r);
                if ((p->rch = u->lic)) {
                    p->rch->par = p;
                    update(p);
                }
                u->lic = r->lip = p;
            }
            u->rch = c;
            update(u);
            c = u;
        }
        splay(v);
        return c;
    }

    // vを根にする
    static void evert(node *v) {
        expose(v);
        flip(v);
    }

    // 非連結であることが保証されている場合
    static void _link(node *p, node *c) {
        evert(c);
        expose(p);
        c->par = p;
        p->rch = c;
        update(p);
    }

    // 辺eを使って繋ぐ(eが孤立点でないと壊れる)
    static void _link_with_edge(node *p, node *e, node *c) {
        evert(c);
        expose(p);
        p->rch = e;
        e->par = p;
        e->lch = nullptr;
        e->rch = c;
        c->par = e;
        update(e);
        update(p);
    }

    // cの親との辺を切る
    static void cut_from_parent(node *c){
        expose(c);
        node *p = c->lch;
        if (p == nullptr) return;
        c->lch = p->par = nullptr;
        update(c);
    }

    // 辺(a, b)があることが保証されている場合
    static void _cut(node *u, node *v) {
        evert(u);
        cut_from_parent(v);
    }

    // 辺eが繋ぐ2頂点を分離(eが次数2でないと壊れる)
    static void _cut_with_edge(node *e) {
        expose(e);
        assert(e->lch && !e->rch && e->lic);
        e->lch->par = nullptr;
        e->lch = nullptr;
        node *r = e->lic->c;
        e->lic = nullptr;
        update(e);
        r->lip = nullptr;
    }

    // 連結なことが保証されている場合
    static node *_lca(node *u, node *v) {
        expose(u);
        return expose(v);
    }
   
    static bool is_there_edge(node *u, node *v) {
        evert(u);
        return u == get_parent(v);
    }

    static node *get_root(node *v) {
        expose(v);
        while (v->lch) {
            push(v);
            v = v->lch;
        }
        splay(v);
        return v;
    }

    static node *get_parent(node *v) {
        expose(v);
        if (!v->lch) return nullptr;// aが根
        push(v);
        v = v->lch;
        while (v->rch) {
            push(v);
            v = v->rch;
        }
        splay(v);
        return v;
    }

    // 同じ連結成分か
    static bool is_same(node *u, node *v) {
        if (!u || !v) return false;
        return get_root(u) == get_root(v);
    }

    static node *centroid(node *v) {
        expose(v);
        W wsum = v->x.wsum;
        if (wsum == 0) return v;
        while (true) {
            W subsum = 0;
            node *u = nullptr, *k = nullptr;
            while (v) {
                k = v;
                push(v);
                W rsum = v->x.w + v->y.wsum + subsum + (v->rch ? v->rch->x.wsum : 0);
                if (wsum <= 2 * rsum) {
                    u = v;
                    v = v->rch;
                } else {
                    subsum = rsum;
                    v = v->lch;
                }
            }
            splay(k);
            v = u;
            if (!v->lic || 2 * v->lic->wmax <= wsum) {
                expose(v);
                return v;
            }
            v = v->lic->wmaxnode;
            splay(v);
        }
    }
};


int main() {
    fast_io<1 << 25, 1 << 24> io;
    int N = io.in();
    int Q = io.in();
    using tree = centroid_dynamic<long long>;
    using node = tree::node;
    std::vector<node*> V(N);
    for (int i = 0; i < N; i++) V[i] = tree::make_node(1);
    map<std::pair<int, int>, node*> mp;
    long long S = 0;
    for (int i = 0; i < Q; i++) {
        int t = io.in();
        if (t == 1) {
            int a = io.in();
            int b = io.in();
            int c = io.in();
            a = (a - 1 + S) % N;
            b = (b - 1 + S) % N;
            auto e = tree::make_edge(c);
            if (a > b) std::swap(a, b);
            mp[{a, b}] = e;
            tree::_link_with_edge(V[a], e, V[b]);
        } else if (t == 2) {
            int a = io.in();
            int b = io.in();
            a = (a - 1 + S) % N;
            b = (b - 1 + S) % N;
            if (a > b) std::swap(a, b);
            auto e = mp[{a, b}];
            //tree::_cut_with_edge(e);
            tree::_cut(V[a], e);
            tree::_cut(V[b], e);
        } else {
            int a = io.in();
            a = (a - 1 + S) % N;
            bool f = V[a]->x.w;
            tree::expose(V[a]);
            V[a]->x.w = !f;
            tree::update(V[a]);
            auto v = tree::centroid(V[a]);
            long long ans = v->x.distsum_rev;
            io.out(ans, '\n');
            S = (S + ans) % N;
        }
    }
}
yukicoder

結果

テストケース

ソースコード
