library_checker/data_structure/
unionfind_with_potential_non_commutative_group.rs

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

library_checker/data_structure/unionfind_with_potential_non_commutative_group.rs

library_checker/data_structure/
unionfind_with_potential_non_commutative_group.rs