Submission #47488116

---

Source Code Expand

#![allow(dead_code)]

pub use __cargo_equip::prelude::*;

use std::collections::HashSet;

use itertools::Itertools;
use minimal_lib_algo::uf::UnionFind;
use proconio::marker::Usize1;
fn main() {
    proconio::input! {
        n: usize,
        m: usize,
        k: usize,
        es: [(Usize1, Usize1, usize); m]
    }
    let mut node_to_edge = vec![vec![]; n];
    for &(u, v, w) in es.iter() {
        node_to_edge[u].push((v, w));
        node_to_edge[v].push((u, w));
    }
    let mut min_cost = k;
    let root = 0;
    {
        let mut tmp = vec![(0, 0)];
        std::mem::swap(&mut node_to_edge[root], &mut tmp);
        for cb in node_to_edge.iter().multi_cartesian_product() {
            let mut uf = UnionFind::new(n);
            let mut ng = false;
            let mut t = 0;
            for (i, &&(v, w)) in cb.iter().enumerate() {
                if i == root {
                    continue;
                }
                if uf.is_unioned(i, v) {
                    ng = true;
                    break;
                }
                uf.union(i, v);
                t += w;
            }
            if !ng {
                min_cost = min_cost.min(t % k);
            }
        }
        std::mem::swap(&mut node_to_edge[root], &mut tmp);
    }
    println!("{}", min_cost);
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `minimal-lib-algo 0.1.0 (path+██████████████████████████████████)` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::minimal_lib_algo`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod minimal_lib_algo {pub mod bisect{use std::ops::{Add,Shr};use std::cmp::PartialOrd;pub fn bisect_predicate_max<T>(mut f:impl FnMut(T)->bool,l:T,r:T)->Option<T>where T:Add<T,Output=T>+Shr<T,Output=T>+PartialOrd+From<i64>+Copy,{let one=1.into();let mut unchanged=true;let mut l=l;let mut r=r+one;while(l+one)<r{let h=(l+r)>>one;if f(h){unchanged=false;l=h;}else{r=h;}}if unchanged&&!f(l){return None;}Some(l)}pub fn bisect_predicate_min<T>(mut f:impl FnMut(T)->bool,l:T,r:T)->Option<T>where T:Add<T,Output=T>+Shr<T,Output=T>+PartialOrd+From<i64>+Copy,{let one=1.into();let mut unchanged=true;let mut l=l;let mut r=r;if!f(r){return None;}while(l+one)<r{let h=(l+r)>>one;if f(h){r=h;}else{unchanged=false;l=h;}}if unchanged&&f(l){return Some(l);}Some(r)}}pub mod compress{use std::{collections::{BTreeMap,HashMap},hash::Hash,};pub struct Compress<T:Hash+Eq+Ord+Clone>{count:usize,vec:Vec<T>,to_index:HashMap<T,usize>,}impl<T:Hash+Eq+Ord+Clone>Compress<T>{pub fn new(it:&[T])->Compress<T>{let mut count=0;let mut last=None;let mut to_index=HashMap::new();let mut vec=vec![];let mut s=it.to_vec();s.sort();for x in s.into_iter(){if let Some(y)=last.take(){if y==x{continue;}}to_index.insert(x.clone(),count);vec.push(x.clone());count+=1;last=Some(x);}Self{count,vec,to_index,}}pub fn is_empty(&self)->bool{self.count==0}pub fn len(&self)->usize{self.count}pub fn get_index(&self,value:T)->usize{self.to_index[&value]}pub fn invert(&self,index:usize)->T{self.vec[index].clone()}}#[derive(Debug)]pub struct SegmentCompress<T:Hash+Eq+Ord+Clone>{count:usize,vec:Vec<T>,to_index:BTreeMap<T,usize>,}impl<T:Hash+Eq+Ord+Clone>SegmentCompress<T>{pub fn new<'a>(it:&[T])->Self{let mut count=0;let mut last=None;let mut to_index=BTreeMap::new();let mut vec=vec![];let mut s=it.to_vec();s.sort();for x in s.into_iter(){if let Some(y)=last.take(){if y==x{last=Some(y);continue;}}to_index.insert(x.clone(),count);vec.push(x.clone());count+=1;last=Some(x);}Self{count,vec,to_index,}}pub fn len(&self)->usize{self.count}pub fn get_index(&self,value:T)->usize{self.to_index[&value]}pub fn get_range(&self,left:T,right:T)->Option<(usize,usize)>{let mut rn=self.to_index.range(left.clone()..right.clone());let mut rn2=self.to_index.range(left..right);Some((*rn.next()?.1,*rn2.next_back()?.1))}pub fn invert(&self,index:usize)->T{self.vec[index].clone()}}}pub mod runlength{pub fn runlength<T>(xs:&[T])->Vec<(T,usize)>where T:Eq+Clone,{let mut result=vec![];let mut run=1;let mut prev_index=0;for(index,item)in xs.iter().enumerate().skip(1){if item==&xs[prev_index]{run+=1;}else{result.push((xs[prev_index].clone(),run));prev_index=index;run=1;}}result.push((xs[prev_index].clone(),run));result}}pub mod uf{pub struct UnionFind{vec:Vec<usize>,component_size:Vec<usize>,}impl UnionFind{pub fn new(size:usize)->Self{let mut vec=Vec::new();let mut component_size=Vec::new();for i in 0..size{vec.push(i);component_size.push(1);}Self{vec,component_size,}}pub fn find_root(&mut self,a:usize)->usize{let mut a=a;let mut stack=Vec::new();loop{let parent=self.vec[a];if parent==a{for i in stack{self.vec[i]=a;}return a;}else{stack.push(a);a=parent;}}}pub fn union(&mut self,a:usize,b:usize){let a_root=self.find_root(a);let b_root=self.find_root(b);if a_root!=b_root{self.vec[a_root]=b_root;self.component_size[b_root]+=self.component_size[a_root];self.component_size[a_root]=0;}}pub fn is_unioned(&mut self,a:usize,b:usize)->bool{self.find_root(a)==self.find_root(b)}}pub trait Group:Default{fn mul(&self,rhs:&Self)->Self;fn inv(&self)->Self;}impl Group for i64{fn mul(&self,rhs:&Self)->Self{self+rhs}fn inv(&self)->Self{-self}}#[derive(Debug)]pub struct UnionFindWith<T:Group>{vec:Vec<(usize,T)>,component_size:Vec<usize>,}impl<T:Group+Copy+std::fmt::Debug>UnionFindWith<T>{pub fn new(size:usize)->Self{let mut vec=Vec::new();let mut component_size=Vec::new();for i in 0..size{vec.push((i,T::default()));component_size.push(1);}Self{vec,component_size,}}pub fn find_root(&mut self,a:usize)->(usize,T){let mut a=a;let mut accum=T::default();let mut stack:Vec<(usize,T)> =Vec::new();loop{let(parent,g)=&self.vec[a];if*parent==a{stack.push((a,accum));let root_accum=accum;for(i,g)in stack.into_iter(){let nx=accum.mul(&g.inv());self.vec[i]=(a,nx);}return(a,root_accum);}else{stack.push((a,accum));accum=accum.mul(g);a=*parent;}}}pub fn union(&mut self,a:usize,b:usize,g:T){let(a_root,ga)=self.find_root(a);let(b_root,gb)=self.find_root(b);if a_root!=b_root{self.vec[a_root]=(b_root,g.mul(&gb.mul(&ga.inv())));self.component_size[b_root]+=self.component_size[a_root];self.component_size[a_root]=0;}}pub fn is_unioned(&mut self,a:usize,b:usize)->Option<T>{let(ra,ga)=self.find_root(a);let(rb,gb)=self.find_root(b);if ra==rb{Some(ga.mul(&gb.inv()))}else{None}}}}pub mod monotone_minima{pub struct MonotoneMinima<'a,T:Ord>{rows:usize,columns:usize,func:Box<dyn 'a+Fn(usize,usize)->T>}impl<'a,T:Ord>MonotoneMinima<'a,T>{pub fn new(rows:usize,columns:usize,func:Box<dyn 'a+Fn(usize,usize)->T>)->Self{Self{rows,columns,func}}fn minima_recur(&self,result:&mut[usize],yl:usize,yr:usize,xl:usize,xr:usize){if yl==yr{return;}let mid=(yl+yr)/2;let mut pos=xl;let mut minimum_value=(self.func)(mid,xl);for i in(xl+1)..xr{let v=(self.func)(mid,i);if v<minimum_value{minimum_value=v;pos=i;}}result[mid]=pos;self.minima_recur(result,yl,mid,xl,pos+1,);self.minima_recur(result,mid+1,yr,pos,xr,);}pub fn minimas(&self)->Vec<usize>{let mut result=vec![0;self.rows];self.minima_recur(&mut result,0,self.rows,0,self.columns);result}}}pub mod interval_set{use std::collections::BTreeMap;#[derive(Debug,Clone,Default)]pub struct IntervalSet<T>where T:Ord+Copy{s:BTreeMap<T,T>,}impl<T>IntervalSet<T>where T:Ord+Copy{pub fn new()->Self{Self{s:BTreeMap::new()}}pub fn get(&self,x:T)->Option<(T,T)>{use std::ops::Bound::*;self.s.range((Unbounded,Included(x))).next_back().filter(|&(_l,r)|x<*r).map(|(x,y)|(*x,*y))}pub fn insert(&mut self,l:T,r:T){use std::ops::Bound::*;let(l,r)=if let Some((il,ir))=self.s.range_mut((Unbounded,Included(l))).next_back(){if l<=*ir{if*ir<r{*ir=r;}(*il,*ir)}else{self.s.insert(l,r);(l,r)}}else{self.s.insert(l,r);(l,r)};while let Some((il,ir))=self.s.range((Unbounded,Included(r))).next_back(){let il=*il;let ir=*ir;if l==il{break;}let cur_seg_r=self.s.get_mut(&l).unwrap();if r<ir{*cur_seg_r=ir;}self.s.remove(&il);}}pub fn remove(&mut self,l:T,r:T){use std::ops::Bound::*;if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(r))).next_back(){if r<*ir{let t=*ir;*ir=l;self.s.insert(r,t);}else if l<*ir{*ir=l;}};while let Some((il,ir))=self.s.range((Included(l),Excluded(r))).next(){let il=*il;let ir=*ir;let cur_seg_r=self.s.get_mut(&il).unwrap();if l<ir{*cur_seg_r=r;}self.s.remove(&il);}if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(l))).next_back(){if l<*ir{*ir=l;}};}pub fn intervals(&self)->Vec<(T,T)>{self.s.iter().map(|(x,y)|(*x,*y)).collect()}pub fn intersect(&mut self,l:T,r:T){use std::ops::Bound::*;while let Some((il,ir))=self.s.range((Unbounded,Excluded(l))).next(){let il=*il;let ir=*ir;self.s.remove(&il);if l<ir{self.s.insert(l,ir);}}while let Some((il,_ir))=self.s.range((Included(r),Unbounded)).next(){let il=*il;self.s.remove(&il);}if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(r))).next_back(){if r<*ir{let _t=*ir;*ir=r;}};}pub fn append(&mut self,new:&Self){for(l,r)in new.intervals().into_iter(){self.insert(l,r);}}}}pub mod permutation{pub fn inverse_permutation(perm:&[usize])->Vec<usize>{let n=perm.len();let mut res=vec![0;n];for i in 0..n{res[perm[i]]=i;}res}pub fn composite_permutation(first:&[usize],second:&[usize])->Vec<usize>{debug_assert_eq!(first.len(),second.len());let n=first.len();let mut res=vec![0;n];for i in 0..n{res[i]=second[first[i]];}res}}pub mod trisect{use std::cmp::PartialOrd;use std::ops::{Add,Div,Sub};pub fn trisect_predicate_min<T,S>(mut f:impl FnMut(T)->S,l:T,r:T)->(T,S)where T:Add<T,Output=T>+Sub<T,Output=T>+Div<T,Output=T>+PartialOrd+From<i64>+Copy+From<i64>+std::fmt::Debug,S:Ord+Clone,{let one=1.into();let two=2.into();let three:T=3.into();let mut l=l;let mut r=r+one;while(l+two)<r{let h1=(l+l+r+one)/three;let h2=(l+r+r)/three;eprintln!("{:?} {:?} {:?} {:?}",l,h1,h2,r);assert!(l<h1);assert!(h1<h2);assert!(h2<r);let cmp=Ord::cmp(&f(h1),&f(h2));match cmp{std::cmp::Ordering::Less=>{r=h2;}std::cmp::Ordering::Equal=>{l=h1;r=h2;}std::cmp::Ordering::Greater=>{l=h1;}}}let mut c=vec![];while l<r{c.push((l,f(l)));l=l+one;}c.into_iter().min_by_key(|x|x.1.clone()).unwrap()}}}
    }

    pub(crate) mod macros {
        pub mod minimal_lib_algo {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod minimal_lib_algo {}
    }
}

Submission Info

Compile Error

warning: unused import: `std::collections::HashSet`
 --> src/main.rs:5:5
  |
5 | use std::collections::HashSet;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

Judge Result