test/yosupo-vertex-set-path-composite.test.cpp

• View this file on GitHub
• Last update: 2025-06-17 22:20:18+02:00
• Problem: https://judge.yosupo.jp/problem/vertex_set_path_composite

Depends on

• graph/graph-template.hpp
• graph/tree/heavy-light-decomposition.hpp
• math/mint.hpp
• structure/segment-tree/segment-tree.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/vertex_set_path_composite
#include <bits/stdc++.h>

#include "../graph/tree/heavy-light-decomposition.hpp"
#include "../math/mint.hpp"
#include "../structure/segment-tree/segment-tree.hpp"

using namespace std;

#ifdef LOCAL
#include "copypaste/debug.h"
#else
#define debug(...) 42
#endif

struct fast_ios {
    fast_ios() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    };
} fast_ios_;

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

struct Info {
    // 默认值
    Mint a, b;
    Info(Mint a = 1, Mint b = 0) : a(a), b(b) {}
    static Info merge(const Info& left_info, const Info& right_info, int l = 0, int r = 0) {
        // a, b -> right_info(left_info)
        Mint a = left_info.a * right_info.a;
        Mint b = right_info.a * left_info.b + right_info.b;

        return Info(a, b);
    }
    string to_string() {
        return "";
    }
};

struct Info2 {
    // 默认值
    Mint a, b;
    Info2(Mint a = 1, Mint b = 0) : a(a), b(b) {}
    static Info2 merge(const Info2& left_info, const Info2& right_info, int l = 0, int r = 0) {
        // a, b -> left(right)
        Mint a = left_info.a * right_info.a;
        Mint b = left_info.a * right_info.b + left_info.b;

        return Info2(a, b);
    }
    string to_string() {
        return "";
    }
};

int main() {
#ifdef LOCAL
    freopen("./data.in", "r", stdin);
#endif
    int n, q;
    cin >> n >> q;
    vector<int> a(n), b(n);
    SegmentTree<Info> st(n);
    SegmentTree<Info2> rev_st(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }

    HeavyLightDecomposition<> hld(n);

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        hld.add_edge(u, v);
    }

    hld.build();
    // debug(hld.rev);

    for (int i = 0; i < n; i++) {
        int u = hld.rev[i];
        st.assign(i, Info(a[u], b[u]));
        rev_st.assign(i, Info2(a[u], b[u]));
    }

    while (q--) {
        int t;
        cin >> t;
        if (t == 0) {
            int p, c, d;
            cin >> p >> c >> d;
            int timestamp = hld.in[p];
            st.assign(timestamp, Info(c, d));
            rev_st.assign(timestamp, Info2(c, d));
        } else {
            int u, v, x;
            cin >> u >> v >> x;
            Info res;
            auto route = hld.dec(u, v);
            for (auto [u, v, flag] : route) {
                if (flag) {
                    Info2 tmp = rev_st.rangeQuery(u, v + 1);
                    res = Info::merge(res, Info(tmp.a, tmp.b));
                } else {
                    Info tmp = st.rangeQuery(u, v + 1);
                    res = Info::merge(res, tmp);
                }
            }
            cout << res.a * x + res.b << endl;
        }
    }
    return 0;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: test/yosupo-vertex-set-path-composite.test.cpp: line 11: unable to process #include in #if / #ifdef / #ifndef other than include guards

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	488 ms	37 MB
g++	almost_line_01	AC	485 ms	38 MB
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	line_00	AC	440 ms	38 MB
g++	line_01	AC	433 ms	39 MB
g++	long-path-decomposition_killer_00	AC	445 ms	33 MB
g++	max_random_00	AC	603 ms	34 MB
g++	max_random_01	AC	527 ms	34 MB
g++	max_random_02	AC	558 ms	34 MB
g++	random_00	AC	384 ms	21 MB
g++	random_01	AC	445 ms	28 MB
g++	random_02	AC	258 ms	11 MB
g++	small_00	AC	7 ms	4 MB
g++	small_01	AC	6 ms	4 MB
g++	small_02	AC	6 ms	4 MB
g++	small_03	AC	7 ms	4 MB
g++	small_04	AC	6 ms	4 MB
g++	worst_for_path_decomposition_00	AC	1164 ms	34 MB
g++	worst_for_path_decomposition_01	AC	1163 ms	34 MB

Back to top page