#976789 (C++17) No.2296 Union Path Query (Hard)

提出ソース

結果

問題	No.2296 Union Path Query (Hard)
ユーザー	👑 Nachia
提出日時	2024-04-23 01:49:16
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	231 ms / 7,000 ms
コード長	6,790 bytes
コンパイル時間	1,594 ms
コンパイル使用メモリ	97,612 KB
実行使用メモリ	15,832 KB
最終ジャッジ日時	2024-04-23 01:49:32
合計ジャッジ時間	12,525 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	8 ms 13,440 KB
testcase_02	AC	6 ms 13,436 KB
testcase_03	AC	7 ms 13,484 KB
testcase_04	AC	120 ms 14,684 KB
testcase_05	AC	144 ms 14,816 KB
testcase_06	AC	136 ms 14,640 KB
testcase_07	AC	150 ms 15,708 KB
testcase_08	AC	148 ms 15,712 KB
testcase_09	AC	125 ms 10,308 KB
testcase_10	AC	130 ms 10,308 KB
testcase_11	AC	160 ms 10,304 KB
testcase_12	AC	129 ms 9,572 KB
testcase_13	AC	85 ms 5,376 KB
testcase_14	AC	82 ms 5,376 KB
testcase_15	AC	162 ms 15,708 KB
testcase_16	AC	155 ms 12,264 KB
testcase_17	AC	118 ms 6,528 KB
testcase_18	AC	231 ms 15,620 KB
testcase_19	AC	172 ms 9,572 KB
testcase_20	AC	209 ms 15,712 KB
testcase_21	AC	186 ms 15,476 KB
testcase_22	AC	203 ms 15,712 KB
testcase_23	AC	129 ms 15,704 KB
testcase_24	AC	107 ms 9,568 KB
testcase_25	AC	113 ms 15,064 KB
testcase_26	AC	107 ms 14,936 KB
testcase_27	AC	144 ms 14,936 KB
testcase_28	AC	148 ms 14,940 KB
testcase_29	AC	190 ms 15,708 KB
testcase_30	AC	160 ms 15,704 KB
testcase_31	AC	146 ms 15,560 KB
testcase_32	AC	153 ms 15,832 KB
testcase_33	AC	166 ms 14,808 KB
testcase_34	AC	129 ms 14,684 KB
testcase_35	AC	133 ms 14,684 KB
testcase_36	AC	183 ms 14,080 KB
testcase_37	AC	166 ms 11,444 KB
testcase_38	AC	166 ms 11,528 KB
testcase_39	AC	156 ms 11,444 KB
testcase_40	AC	163 ms 12,212 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	2 ms 5,376 KB
testcase_43	AC	1 ms 5,376 KB
testcase_44	AC	144 ms 15,708 KB
testcase_45	AC	148 ms 15,708 KB
testcase_46	AC	185 ms 15,612 KB
testcase_47	AC	155 ms 15,708 KB
testcase_48	AC	152 ms 15,712 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <vector>
#include <algorithm>

namespace nachia {

struct IncrementalForest{
    struct Node {
        int jump;
        int parent;
        int parentEdge;
        int depth;
        int child;
        int brother;
    };
    std::vector<Node> nodes;
    std::vector<int> dsu;
    std::vector<bool> todbl;
    int edgeIndex;
    void makeToDbl(int x){
        while(int(todbl.size()) < x){
            int z = int(todbl.size());
            todbl.resize(z*2+1);
            std::copy(todbl.begin(), todbl.begin() + z, todbl.begin() + z);
            todbl[z*2] = true;
        }
    }
    IncrementalForest(int n = 0){
        nodes.assign(n, { -1, -1, -1, 0, -1, -1 });
        dsu.assign(n, -1);
        todbl.assign(1, false);
        makeToDbl(n);
        edgeIndex = 0;
    }
    int rootOf(int u){
        if(dsu[u] < 0) return u;
        return dsu[u] = rootOf(dsu[u]);
    }
    bool areConnected(int u, int v){ return rootOf(u) == rootOf(v); }
    int componentSize(int u){ return -dsu[rootOf(u)]; }
    int numVertices(){ return nodes.size(); }
    int addNode(){
        int v = numVertices();
        nodes.push_back({ -1, -1, -1, 0, -1, -1 });
        makeToDbl(numVertices());
        return v;
    }
    int addEdge(int u, int v){
        std::vector<int> bfs;
        {
            int ru = rootOf(u);
            int rv = rootOf(v);
            if(ru == rv) return -1;
            if(-dsu[ru] < -dsu[rv]){ std::swap(u, v); std::swap(ru, rv); }
            bfs = std::vector<int>(-dsu[rv]);
            dsu[ru] += dsu[rv];
            dsu[rv] = ru;
        }
        int e = edgeIndex++;
        int bfsp = 0;
        auto setParent = [&](int v, int p) -> void {
            nodes[v].parent = p;
            nodes[v].depth = nodes[p].depth + 1;
            nodes[v].jump = todbl[nodes[v].depth - 1] ? nodes[nodes[p].jump].jump : p;
        };
        int p = u;
        int p2 = v;
        for(int x=nodes[v].child; x>=0; x=nodes[x].brother) bfs[bfsp++] = x;
        while(nodes[p2].parent >= 0){
            int w = nodes[p2].parent;
            for(int *pc=&nodes[w].child; *pc>=0; ){
                int x = *pc;
                if(x == p2){
                    *pc = nodes[x].brother;
                    std::swap(nodes[p2].parentEdge, e);
                    nodes[p2].brother = nodes[p].child;
                    nodes[p].child = p2;
                    setParent(p2, p);
                } else {
                    bfs[bfsp++] = x;
                    pc = &nodes[x].brother;
                }
            }
            p = p2; p2 = w;
        }
        std::swap(nodes[p2].parentEdge, e);
        nodes[p2].brother = nodes[p].child;
        nodes[p].child = p2;
        setParent(p2, p);
        for(int i=0; i<bfsp; i++){
            int w = bfs[i];
            setParent(w, nodes[w].parent);
            for(int x=nodes[w].child; x>=0; x=nodes[x].brother) bfs[bfsp++] = x;
        }
        return edgeIndex - 1;
    }
    int parentOf(int u){ return nodes[u].parent; }
    int parentEdgeOf(int u){ return nodes[u].parentEdge; }
    int depth(int u){ return nodes[u].depth; }
    int lca(int u, int v){
        if(!areConnected(u, v)) return -1;
        if(depth(u) < depth(v)) std::swap(u, v);
        int dv = depth(v);
        while(depth(u) != dv){
            u = (depth(nodes[u].jump) >= dv ? nodes[u].jump : nodes[u].parent);
        }
        while(u != v){
            if(nodes[u].jump != nodes[v].jump){
                u = nodes[u].jump;
                v = nodes[v].jump;
            } else {
                u = nodes[u].parent;
                v = nodes[v].parent;
            }
        }
        return u;
    }
    int middle(int u, int v, int w){
        if(!areConnected(u, v) || !areConnected(v, w)) return -1;
        return lca(u,v) ^ lca(v,w) ^ lca(w,u);
    }
    int dist(int u, int v){
        if(!areConnected(u, v)) return -1;
        return depth(u) - depth(lca(u, v)) * 2 + depth(v);
    }
    
    struct ChildrenIterRange {
    struct Iter {
        std::vector<Node>::iterator nodes; int v;
        int operator*() const { return v; }
        Iter& operator++(){ v = nodes[v].brother; return *this; }
        Iter operator++(int) const { auto a = *this; return ++a; }
        bool operator==(Iter& r) const { return v == r.v; }
        bool operator!=(Iter& r) const { return v != r.v; }
    };
        std::vector<Node>::iterator nodes; int v;
        Iter begin() const { return { nodes, nodes[v].child }; }
        Iter end() const { return { nodes, -1 }; }
    };
    ChildrenIterRange children(int v){
        return ChildrenIterRange{ nodes.begin(), v };
    }
};

} // namespace nachia


#include <iostream>
#include <string>

int main(){
    using namespace std;
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N, X, Q; cin >> N >> X >> Q;
    nachia::IncrementalForest forest(N);
    std::vector<long long> depth(N);
    std::vector<long long> weight;
    struct Diam { long long d; int v; int w; };
    std::vector<Diam> diam(N);
    for(int i=0; i<N; i++) diam[i] = { 0,i,i };
    auto dist = [&](int u, int v) -> long long {
        int g = forest.lca(u, v);
        if(g < 0) return -1;
        long long d = depth[u] - 2 * depth[g] + depth[v];
        return d;
    };
    auto mergeDiam = [&](Diam l, Diam r) -> Diam {
        Diam res = l;
        if(res.d < r.d) res = r;
        auto upd = [&](int v, int w){
            long long d = dist(v,w);
            if(res.d < d) res = { d,v,w };
        };
        upd(l.v, r.v);
        upd(l.v, r.w);
        upd(l.w, r.v);
        upd(l.w, r.w);
        return res;
    };
    for(int qi=0; qi<Q; qi++){
        int t; cin >> t;
        if(t == 1){
            int v, w; cin >> v >> w;
            int u = X;
            int ur = forest.rootOf(u);
            int vr = forest.rootOf(v);
            if(forest.addEdge(u, v) < 0) exit(1);
            int xr = forest.rootOf(v);
            weight.push_back(w);
            if(forest.parentOf(v) != u) std::swap(u, v);
            std::vector<int> bfs;
            bfs.push_back(v);
            for(int i=0; i<int(bfs.size()); i++){
                int x = bfs[i];
                depth[x] = depth[forest.parentOf(x)] + weight[forest.parentEdgeOf(x)];
                for(int y : forest.children(x)) bfs.push_back(y);
            }
            diam[xr] = mergeDiam(diam[ur], diam[vr]);
        }
        if(t == 2){
            int u, v; cin >> u >> v;
            long long d = dist(u, v);
            cout << d << '\n';
            if(d != -1) X = (X + d) % N;
        }
        if(t == 3){
            int v; cin >> v;
            cout << diam[forest.rootOf(v)].d << '\n';
        }
        if(t == 4){
            int v; cin >> v;
            X = (X + v) % N;
        }
    }
    return 0;
}

yukicoder

結果

テストケース

ソースコード