library_checker/data_structure/
unionfind_with_potential_non_commutative_group.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::{Associative, Invertible, Magma, Unital},
5    data_structure::PotentializedUnionFind,
6    define_monoid,
7    num::{One, Zero, montgomery::MInt998244353},
8};
9
10competitive::define_enum_scan! {
11    enum Query: u8 {
12        0 => Unite { u: usize, v: usize, x: [[MInt998244353; const 2]; const 2] }
13        1 => Diff { u: usize, v: usize }
14    }
15}
16
17define_monoid!(
18    Sl2,
19    [[MInt998244353; 2]; 2],
20    |a, b| {
21        let [[a00, a01], [a10, a11]] = a;
22        let [[b00, b01], [b10, b11]] = b;
23        [
24            [a00 * b00 + a01 * b10, a00 * b01 + a01 * b11],
25            [a10 * b00 + a11 * b10, a10 * b01 + a11 * b11],
26        ]
27    },
28    [
29        [MInt998244353::one(), MInt998244353::zero()],
30        [MInt998244353::zero(), MInt998244353::one()]
31    ]
32);
33
34impl Invertible for Sl2 {
35    fn inverse(x: &Self::T) -> Self::T {
36        [[x[1][1], -x[0][1]], [-x[1][0], x[0][0]]]
37    }
38}
39
40#[verify::library_checker("unionfind_with_potential_non_commutative_group")]
41pub fn unionfind_with_potential_non_commutative_group(reader: impl Read, mut writer: impl Write) {
42    let s = read_all_unchecked(reader);
43    let mut scanner = Scanner::new(&s);
44    scan!(scanner, n, q);
45    let mut uf = PotentializedUnionFind::<Sl2>::new(n);
46    for _ in 0..q {
47        scan!(scanner, query: Query);
48        match query {
49            Query::Unite { u, v, x } => {
50                if let Some(diff) = uf.difference(v, u) {
51                    writeln!(writer, "{}", (diff == x) as u8).ok();
52                } else {
53                    uf.unite_with(v, u, x);
54                    writeln!(writer, "1").ok();
55                }
56            }
57            Query::Diff { u, v } => {
58                if let Some(diff) = uf.difference(v, u) {
59                    iter_print!(writer, @it diff.into_iter().flatten());
60                } else {
61                    writeln!(writer, "-1").ok();
62                }
63            }
64        }
65    }
66}

library_checker/data_structure/unionfind_with_potential_non_commutative_group.rs

library_checker/data_structure/
unionfind_with_potential_non_commutative_group.rs