#632900 (C++17) No.399 動的な領主

提出ソース

結果

問題	No.399 動的な領主
ユーザー	lorent_kyopro
提出日時	2021-03-21 23:28:01
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	586 ms / 2,000 ms
コード長	6,097 bytes
コンパイル時間	2,609 ms
コンパイル使用メモリ	222,040 KB
実行使用メモリ	24,880 KB
最終ジャッジ日時	2024-05-02 06:54:14
合計ジャッジ時間	8,366 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	4 ms 5,376 KB
testcase_05	AC	33 ms 5,376 KB
testcase_06	AC	576 ms 19,840 KB
testcase_07	AC	556 ms 19,968 KB
testcase_08	AC	559 ms 19,968 KB
testcase_09	AC	568 ms 19,968 KB
testcase_10	AC	5 ms 5,376 KB
testcase_11	AC	25 ms 5,376 KB
testcase_12	AC	403 ms 20,224 KB
testcase_13	AC	381 ms 20,312 KB
testcase_14	AC	89 ms 24,812 KB
testcase_15	AC	127 ms 24,880 KB
testcase_16	AC	210 ms 22,912 KB
testcase_17	AC	586 ms 19,968 KB
testcase_18	AC	574 ms 19,840 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>

__attribute__((constructor))
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

class heavy_light_decomposition {
public:
    heavy_light_decomposition(size_t n)
        : n(n),
          tree(n),
          subtree_size(n, 1),
          parent(n),
          in(n),
          out(n),
          chain_head(n),
          built(false) {}

    heavy_light_decomposition(const std::vector<std::vector<size_t>>& tree)
        : heavy_light_decomposition(tree, 0) {}

    heavy_light_decomposition(const std::vector<std::vector<size_t>>& tree,
                              size_t root)
        : n(tree.size()),
          tree(tree),
          subtree_size(n, 1),
          parent(n),
          in(n),
          out(n),
          chain_head(n),
          built(false) {
        assert(root < n);
        build(root);
    }

    void add_edge(size_t u, size_t v) {
        assert(u < n && v < n);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    void build(size_t root = 0) {
        dfs_for_size(0, n);
        size_t time = 0;
        chain_head[root] = root;
        dfs_for_hld(root, time);
        built = true;
    }

    size_t operator[](size_t u) const {
        assert(built && u < n);
        return in[u];
    }

    size_t lca(size_t u, size_t v) const {
        assert(built && u < n && v < n);
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] == chain_head[v]) return u;
            v = parent[chain_head[v]];
        }
    }

    std::pair<size_t, size_t> subtree_query(size_t u) const {
        assert(built && u < n);
        return {in[u], out[u]};
    }
    
    template <typename F> void subtree_query(size_t u, const F& f) const {
        assert(built && u < n);
        f(in[u], out[u]);
    }

    // when operation is noncommutative

    // S resl = e(), resr = e();
    // size_t w = hld.lca(u, v)
    // hld.node_query(u, w, [&](size_t l, size_t r) { resl = op(resl, rseg.prod(l, r)); });
    // hld.edge_query(w, v, [&](size_t l, size_t r) { resr = op(seg.prod(l, r), resr); });
    // S res = op(resl, resr);

    std::vector<std::pair<size_t, size_t>> node_query(size_t u, size_t v) const {
        assert(built && u < n && v < n);
        std::vector<std::pair<size_t, size_t>> result;
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                result.emplace_back(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                result.emplace_back(in[u], in[v] + 1);
                return result;
            }
        }
    }

    template <typename F> void node_query(size_t u, size_t v, const F& f) const {
        assert(built && u < n && v < n);
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                f(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                f(in[u], in[v] + 1);
                return;
            }
        }
    }

    std::vector<std::pair<size_t, size_t>> edge_query(size_t u, size_t v) const {
        assert(built && u < n && v < n);
        std::vector<std::pair<size_t, size_t>> result;
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                result.emplace_back(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                if (u != v) result.emplace_back(in[u] + 1, in[v] + 1);
                return result;
            }
        }
    }

    template <typename F> void edge_query(size_t u, size_t v, const F& f) const {
        assert(built && u < n && v < n);
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                f(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                if (u != v) f(in[u] + 1, in[v] + 1);
                return;
            }
        }
    }

private:
    const size_t n;
    std::vector<std::vector<size_t>> tree;
    std::vector<size_t> subtree_size, parent, in, out, chain_head;
    bool built;

    void dfs_for_size(size_t u, size_t p) {
        parent[u] = p;
        if (!tree[u].empty() && tree[u].front() == p)
            std::swap(tree[u].front(), tree[u].back());
        for (size_t& v : tree[u]) {
            if (v == p) continue;
            dfs_for_size(v, u);
            subtree_size[u] += subtree_size[v];
            if (subtree_size[v] > subtree_size[tree[u].front()]) {
                std::swap(v, tree[u].front());
            }
        }
    }

    void dfs_for_hld(size_t u, size_t& time) {
        in[u] = time++;
        for (size_t& v : tree[u]) {
            if (v == parent[u]) continue;
            chain_head[v] = (v == tree[u].front() ? chain_head[u] : v);
            dfs_for_hld(v, time);
        }
        out[u] = time;
    }
};

using S = std::pair<long long, size_t>;
S op(S a, S b) { return {a.first + b.first, a.second + b.second}; }
S e() { return {0, 0}; }
using F = long long;
S mapping(F f, S x) { return {x.first + f * x.second, x.second}; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

int main() {
    size_t n;
    std::cin >> n;

    heavy_light_decomposition hld(n);
    for (size_t i = 0; i < n - 1; ++i) {
        size_t u, v;
        std::cin >> u >> v;
        u--; v--;
        hld.add_edge(u, v);
    }
    hld.build();
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(std::vector<S>(n, {0, 1}));

    size_t q;
    std::cin >> q;
    long long ans = 0;
    while (q--) {
        size_t a, b;
        std::cin >> a >> b;
        a--; b--;
        hld.node_query(a, b, [&](size_t l, size_t r) {
            seg.apply(l, r, 1);
            ans += seg.prod(l, r).first;
        });
    }
    std::cout << ans << '\n';
}

yukicoder

結果

テストケース

ソースコード