library_checker/data_structure/
unionfind_with_potential.rs1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4 algebra::AdditiveOperation, data_structure::PotentializedUnionFind,
5 num::montgomery::MInt998244353,
6};
7
8competitive::define_enum_scan! {
9 enum Query: u8 {
10 0 => Unite { u: usize, v: usize, x: MInt998244353 }
11 1 => Diff { u: usize, v: usize }
12 }
13}
14
15#[verify::library_checker("unionfind_with_potential")]
16pub fn unionfind_with_potential(reader: impl Read, mut writer: impl Write) {
17 let s = read_all_unchecked(reader);
18 let mut scanner = Scanner::new(&s);
19 scan!(scanner, n, q);
20 let mut uf = PotentializedUnionFind::<AdditiveOperation<MInt998244353>>::new(n);
21 for _ in 0..q {
22 scan!(scanner, query: Query);
23 match query {
24 Query::Unite { u, v, x } => {
25 if let Some(diff) = uf.difference(u, v) {
26 writeln!(writer, "{}", (diff == x) as u8).ok();
27 } else {
28 uf.unite_with(u, v, x);
29 writeln!(writer, "1").ok();
30 }
31 }
32 Query::Diff { u, v } => {
33 if let Some(diff) = uf.difference(u, v) {
34 writeln!(writer, "{}", diff).ok();
35 } else {
36 writeln!(writer, "-1").ok();
37 }
38 }
39 }
40 }
41}