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

提出ソース

結果

問題	No.2296 Union Path Query (Hard)
ユーザー	👑 Nachia
提出日時	2024-04-23 01:20:50
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	213 ms / 7,000 ms
コード長	6,720 bytes
コンパイル時間	1,576 ms
コンパイル使用メモリ	99,528 KB
実行使用メモリ	15,832 KB
最終ジャッジ日時	2024-10-15 00:34:45
合計ジャッジ時間	15,739 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	10 ms 13,440 KB
testcase_02	AC	9 ms 13,440 KB
testcase_03	AC	10 ms 13,440 KB
testcase_04	AC	122 ms 14,680 KB
testcase_05	AC	131 ms 14,808 KB
testcase_06	AC	159 ms 14,684 KB
testcase_07	AC	149 ms 15,708 KB
testcase_08	AC	145 ms 15,580 KB
testcase_09	AC	135 ms 10,308 KB
testcase_10	AC	135 ms 10,308 KB
testcase_11	AC	133 ms 10,180 KB
testcase_12	AC	131 ms 9,444 KB
testcase_13	AC	92 ms 5,248 KB
testcase_14	AC	85 ms 5,248 KB
testcase_15	AC	163 ms 15,832 KB
testcase_16	AC	163 ms 12,140 KB
testcase_17	AC	124 ms 6,400 KB
testcase_18	AC	213 ms 15,580 KB
testcase_19	AC	178 ms 9,572 KB
testcase_20	AC	208 ms 15,708 KB
testcase_21	AC	199 ms 15,712 KB
testcase_22	AC	201 ms 15,580 KB
testcase_23	AC	118 ms 15,700 KB
testcase_24	AC	104 ms 9,440 KB
testcase_25	AC	97 ms 14,808 KB
testcase_26	AC	96 ms 14,808 KB
testcase_27	AC	131 ms 14,804 KB
testcase_28	AC	129 ms 14,808 KB
testcase_29	AC	131 ms 15,576 KB
testcase_30	AC	134 ms 15,704 KB
testcase_31	AC	146 ms 15,828 KB
testcase_32	AC	149 ms 15,704 KB
testcase_33	AC	160 ms 15,320 KB
testcase_34	AC	126 ms 14,812 KB
testcase_35	AC	125 ms 14,688 KB
testcase_36	AC	183 ms 14,296 KB
testcase_37	AC	154 ms 12,208 KB
testcase_38	AC	155 ms 12,172 KB
testcase_39	AC	152 ms 12,212 KB
testcase_40	AC	157 ms 12,596 KB
testcase_41	AC	2 ms 5,248 KB
testcase_42	AC	2 ms 5,248 KB
testcase_43	AC	2 ms 5,248 KB
testcase_44	AC	141 ms 15,636 KB
testcase_45	AC	143 ms 15,520 KB
testcase_46	AC	148 ms 15,704 KB
testcase_47	AC	149 ms 15,708 KB
testcase_48	AC	151 ms 15,708 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);
            auto dfs = [&](auto& dfs, int x) -> void {
                depth[x] = depth[forest.parentOf(x)] + weight[forest.parentEdgeOf(x)];
                for(int y : forest.children(x)) dfs(dfs, y);
            };
            dfs(dfs, v);
            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

結果

テストケース

ソースコード