aizu_online_judge/dsl/
dsl_1_b.rs1use competitive::prelude::*;
2use competitive::{algebra::AdditiveOperation, data_structure::PotentializedUnionFind};
3
4competitive::define_enum_scan! {
5 enum Query: usize {
6 0 => Unite { x: usize, y: usize, w: i64 }
7 1 => Diff { x: usize, y: usize }
8 }
9}
10
11#[verify::aizu_online_judge("DSL_1_B")]
12pub fn dsl_1_b(reader: impl Read, writer: impl Write) {
13 prepare_io!(reader, writer);
14 sc!(n, q);
15 let mut uf = PotentializedUnionFind::<AdditiveOperation<_>>::new(n);
16 for _ in 0..q {
17 sc!(query: Query);
18 match query {
19 Query::Unite { x, y, w } => {
20 uf.unite_with(x, y, w);
21 }
22 Query::Diff { x, y } => {
23 if let Some(w) = uf.difference(x, y) {
24 pp!(w);
25 } else {
26 pp!("?");
27 }
28 }
29 }
30 }
31}