library-rs

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub naoya675/library-rs

:heavy_check_mark: verification/library-checker/vertex_set_path_composite/src/main.rs

Depends on

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/vertex_set_path_composite

use proconio::input;

use euler_tour::EulerTour;
use modint::StaticModint;
use segment_tree::SegmentTree;

type Mint = StaticModint<998244353>;

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024)
        .spawn(actual_main)
        .unwrap()
        .join()
        .unwrap();
}

fn actual_main() {
    input! {
        n: usize,
        q: usize,
        ab: [(u64, u64); n],
        uv: [(usize, usize); n - 1],
    }
    let mut et = EulerTour::<usize>::new(n);
    for (u, v) in uv {
        et.add_edge(u, v, 0);
        et.add_edge(v, u, 0);
    }
    et.init(0);
    let val = |a: u64, b: u64| (Mint::new(a), Mint::new(b));
    let invval = |a: u64, b: u64| (Mint::new(1) / Mint::new(a), -Mint::new(b) / Mint::new(a));
    let mut st1 = SegmentTree::<(Mint, Mint)>::new(n + n, |a, b| (a.0 * b.0, a.1 * b.0 + b.1), val(1, 0));
    let mut st2 = SegmentTree::<(Mint, Mint)>::new(n + n, |b, a| (a.0 * b.0, a.1 * b.0 + b.1), val(1, 0));
    for i in 0..n {
        let (a, b) = ab[i];
        let index = et.index(i);
        st1.set(index.0, val(a, b));
        st2.set(index.0, val(a, b));
        st1.set(index.1, invval(a, b));
        st2.set(index.1, invval(a, b));
    }
    for _ in 0..q {
        input! { query: usize, }
        match query {
            0 => {
                input! { p: usize, c: u64, d: u64 }
                let index = et.index(p);
                st1.set(index.0, val(c, d));
                st2.set(index.0, val(c, d));
                st1.set(index.1, invval(c, d));
                st2.set(index.1, invval(c, d));
            }
            1 => {
                input! { u: usize, v: usize, x: u64 }
                let x = std::cell::RefCell::new(Mint::new(x));
                et.for_each_with(
                    u,
                    v,
                    |l, r| {
                        let (a, b) = st1.prod(l, r);
                        let tmp = *x.borrow() * a + b;
                        *x.borrow_mut() = tmp;
                    },
                    |l, r| {
                        let (a, b) = st2.prod(l, r);
                        let tmp = *x.borrow() * a + b;
                        *x.borrow_mut() = tmp;
                    },
                );
                println!("{}", x.into_inner());
            }
            _ => unreachable!(),
        }
    }
}
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError
Back to top page