#934850 (Rust) No.2563 色ごとのグループ

• 問題: No.2563 色ごとのグループ
• ユーザー: あさくち
• 提出日時: 2023-12-02 15:58:16
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 184 ms / 2,000 ms
• コード長: 15,978 bytes
• コンパイル時間: 1,553 ms
• コンパイル使用メモリ: 208,580 KB
• 実行使用メモリ: 41,712 KB
• 最終ジャッジ日時: 2023-12-02 15:58:24
• 合計ジャッジ時間: 5,031 ms
• ジャッジサーバーID （参考情報）: judge15 / judge9

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,548 KB
testcase_01	AC	1 ms; 6,548 KB
testcase_02	AC	1 ms; 6,548 KB
testcase_03	AC	1 ms; 6,548 KB
testcase_04	AC	1 ms; 6,548 KB
testcase_05	AC	1 ms; 6,548 KB
testcase_06	AC	1 ms; 6,548 KB
testcase_07	AC	1 ms; 6,548 KB
testcase_08	AC	1 ms; 6,548 KB
testcase_09	AC	1 ms; 6,548 KB
testcase_10	AC	1 ms; 6,548 KB
testcase_11	AC	1 ms; 6,548 KB
testcase_12	AC	1 ms; 6,548 KB
testcase_13	AC	1 ms; 6,548 KB
testcase_14	AC	1 ms; 6,548 KB
testcase_15	AC	1 ms; 6,548 KB
testcase_16	AC	2 ms; 6,548 KB
testcase_17	AC	1 ms; 6,548 KB
testcase_18	AC	1 ms; 6,548 KB
testcase_19	AC	3 ms; 6,548 KB
testcase_20	AC	10 ms; 6,548 KB
testcase_21	AC	5 ms; 6,548 KB
testcase_22	AC	4 ms; 6,548 KB
testcase_23	AC	7 ms; 6,548 KB
testcase_24	AC	68 ms; 19,928 KB
testcase_25	AC	59 ms; 20,220 KB
testcase_26	AC	87 ms; 28,564 KB
testcase_27	AC	105 ms; 33,728 KB
testcase_28	AC	99 ms; 31,900 KB
testcase_29	AC	158 ms; 41,696 KB
testcase_30	AC	159 ms; 41,712 KB
testcase_31	AC	155 ms; 41,708 KB
testcase_32	AC	184 ms; 41,708 KB
testcase_33	AC	150 ms; 38,368 KB
testcase_34	AC	150 ms; 38,292 KB
testcase_35	AC	156 ms; 38,300 KB
testcase_36	AC	149 ms; 38,368 KB
testcase_37	AC	149 ms; 38,372 KB

ソースコード

pub use __cargo_equip::prelude::*;

use std::collections::HashSet;

use procon_library_rs::disjoint_set::DisjointSet;

fn main() {
    let (n, m) = input_tuple();
    let c = input_vec::<usize>();
    let u_v = input_tuple_vec::<usize>(m);

    let mut list = vec![Vec::new(); n];

    let mut uf = DisjointSet::new(n);

    for &(u, v) in &u_v {
        list[u - 1].push(v - 1);
        list[v - 1].push(u - 1);

        if c[u - 1] == c[v - 1] {
            uf.unite(u - 1, v - 1);
        }
    }

    let mut colors = vec![HashSet::new(); n];

    for i in 0..n {
        colors[c[i] - 1].insert(i);
    }

    let mut result = 0_usize;

    for color in 0..n {
        if colors[color].len() == 0 {
            continue;
        }

        let &base = colors[color].iter().next().unwrap();

        // colors[i]内の頂点が全て連結であれば良い

        for &v in colors[color].iter() {
            if !uf.same(base, v) {
                // println!("color {} base {} v {}", color, base, v);

                result += 1;
                uf.unite(base, v);
            }
        }
    }

    println!("{}", result);
}

fn input_tuple<T>() -> (T, T)
where
    T: std::str::FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    let stdin = std::io::stdin();

    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf = buf.trim_end().to_owned();

    let mut iter = buf.split_whitespace();

    let n = iter.next().unwrap().parse().unwrap();
    let m = iter.next().unwrap().parse().unwrap();

    (n, m)
}

fn input_vec<T>() -> Vec<T>
where
    T: std::str::FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    let stdin = std::io::stdin();

    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf = buf.trim_end().to_owned();

    let iter = buf.split_whitespace();

    let line = iter.map(|x| x.parse().unwrap()).collect();

    line
}

fn input_tuple_vec<T>(n: usize) -> Vec<(T, T)>
where
    T: std::str::FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    // タプルのベクタ

    let stdin = std::io::stdin();

    let mut s_t_d = Vec::with_capacity(n);

    for _ in 0..n {
        let mut buf = String::new();
        stdin.read_line(&mut buf).unwrap();
        buf = buf.trim_end().to_owned();

        let mut iter = buf.split_whitespace();

        let s = iter.next().unwrap().parse().unwrap();
        let t = iter.next().unwrap().parse().unwrap();
        // let d = iter.next().unwrap().parse().unwrap();

        s_t_d.push((s, t));
    }

    s_t_d
}

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

///  # Bundled libraries
/// 
///  - `procon-library-rs 0.1.0 (path+██████████████████████████████████████████████████████████████████)` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::procon_library_rs`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod procon_library_rs {pub use crate::__cargo_equip::macros::procon_library_rs::*;pub mod binary_indexed_tree{pub struct BinaryIndexedTree{n:usize,bit:Vec<isize>,}impl BinaryIndexedTree{pub fn new(n:usize)->BinaryIndexedTree{let bit=vec![0;n+1];BinaryIndexedTree{n:n+1,bit}}pub fn add(&mut self,i:usize,x:isize){assert_ne!(i,0,"i is 1-index");let mut index=i as isize;while(index as usize)<self.n{self.bit[index as usize]+=x;index+=index&-index;}}pub fn sum(&self,i:usize)->isize{assert_ne!(i,0,"i is 1-index");let mut s=0;let mut index=i as isize;while index>0{s+=self.bit[index as usize];index-=index&-index;}s}}}pub mod disjoint_set{#[derive(Debug)]pub struct DisjointSet{rank:Vec<usize>,parent:Vec<usize>,diff_weight:Vec<isize>,}impl DisjointSet{pub fn new(n:usize)->DisjointSet{DisjointSet{rank:vec![0;n],parent:(0..n).collect::<Vec<_>>(),diff_weight:vec![0;n],}}pub fn find_set(&mut self,x:usize)->usize{if x!=self.parent[x]{let r=self.find_set(self.parent[x]);self.diff_weight[x]+=self.diff_weight[self.parent[x]];self.parent[x]=r;}self.parent[x]}pub fn unite(&mut self,x:usize,y:usize){self.unite_weight(x,y,0);}pub fn unite_weight(&mut self,x:usize,y:usize,w:isize){let mut w=w+self.weight(x)-self.weight(y);let mut x=self.find_set(self.parent[x]);let mut y=self.find_set(self.parent[y]);if self.rank[x]<self.rank[y]{std::mem::swap(&mut x,&mut y);w=-w;}if self.rank[x]==self.rank[y]{self.rank[x]+=1;}self.parent[y]=x;self.diff_weight[y]=w;}pub fn same(&mut self,x:usize,y:usize)->bool{self.find_set(x)==self.find_set(y)}pub fn weight(&mut self,x:usize)->isize{self.find_set(x);self.diff_weight[x]}pub fn diff(&mut self,x:usize,y:usize)->isize{self.weight(y)-self.weight(x)}}}pub mod doubling{pub struct Doubling{n:usize,log_k:usize,doubling:Vec<Vec<usize>>,}impl Doubling{pub fn new(k:usize,one_step:&Vec<usize>)->Doubling{let n=one_step.len();let mut log_k=0;while 1<<log_k<=k{log_k+=1;}let mut doubling=vec![vec![0;n];log_k+1];doubling[0]=one_step.clone();Doubling{n,log_k,doubling}}pub fn preprocess(&mut self){for j in 0..self.log_k{for i in 0..self.n{self.doubling[j+1][i]=self.doubling[j][self.doubling[j][i]];}}}pub fn get(&self,k:usize,start:usize)->usize{let mut current=start;for i in(0..self.log_k).rev(){if k&(1<<i)>0{current=self.doubling[i][current];}}current}}}pub mod geometry{pub mod angle{#[derive(Copy,Clone,PartialEq,Debug)]pub struct Degree(pub f64);#[derive(Copy,Clone,PartialEq,Debug)]pub struct Radian(pub f64);impl std::ops::Add for Degree{type Output=Degree;fn add(self,rhs:Self)->Self{Degree(self.0+rhs.0)}}impl std::ops::Sub for Degree{type Output=Degree;fn sub(self,rhs:Self)->Self{Degree(self.0-rhs.0)}}impl std::ops::Mul<f64>for Degree{type Output=Degree;fn mul(self,k:f64)->Self{Degree(self.0*k)}}impl std::ops::Div<f64>for Degree{type Output=Degree;fn div(self,k:f64)->Self{Degree(self.0/k)}}impl std::ops::Add for Radian{type Output=Radian;fn add(self,rhs:Self)->Self{Radian(self.0+rhs.0)}}impl std::ops::Sub for Radian{type Output=Radian;fn sub(self,rhs:Self)->Self{Radian(self.0-rhs.0)}}impl std::ops::Mul<f64>for Radian{type Output=Radian;fn mul(self,k:f64)->Self{Radian(self.0*k)}}impl std::ops::Div<f64>for Radian{type Output=Radian;fn div(self,k:f64)->Self{Radian(self.0/k)}}trait ToDegree{fn to_degree(&self)->Degree;}impl ToDegree for f64{fn to_degree(&self)->Degree{Degree(*self)}}impl ToDegree for Radian{fn to_degree(&self)->Degree{Degree(self.0*180./std::f64::consts::PI)}}pub trait ToRadian{fn to_radian(&self)->Radian;}impl ToRadian for f64{fn to_radian(&self)->Radian{Radian(*self)}}impl ToRadian for Degree{fn to_radian(&self)->Radian{Radian(self.0*std::f64::consts::PI/180.)}}}pub mod point2f{use super::angle::*;use super::prelude::*;#[derive(Copy,Clone,PartialEq,Debug)]pub struct Point2f{pub x:f64,pub y:f64,}impl std::ops::Add for Point2f{type Output=Point2f;fn add(self,rhs:Self)->Self{Point2f{x:self.x+rhs.x,y:self.y+rhs.y,}}}impl std::ops::Sub for Point2f{type Output=Point2f;fn sub(self,rhs:Self)->Self{Point2f{x:self.x-rhs.x,y:self.y-rhs.y,}}}impl std::ops::Mul<f64>for Point2f{type Output=Point2f;fn mul(self,k:f64)->Self{Point2f{x:self.x*k,y:self.y*k,}}}impl std::ops::Div<f64>for Point2f{type Output=Point2f;fn div(self,k:f64)->Self{Point2f{x:self.x/k,y:self.y/k,}}}impl std::fmt::Display for Point2f{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{} {}",self.x,self.y)}}impl Point2f{pub const ZERO:Point2f=Point2f{x:0.,y:0.};pub const ONE:Point2f=Point2f{x:1.,y:1.};pub fn new(x:f64,y:f64)->Point2f{Point2f{x,y}}pub fn norm(&self)->f64{self.x*self.x+self.y*self.y}pub fn abs(&self)->f64{self.norm().sqrt()}pub fn manhattan_distance(&self,rhs:Point2f)->f64{(self.x-rhs.x).abs()+(self.y-rhs.y).abs()}pub fn euclidean_distance(&self,rhs:Point2f)->f64{((self.x-rhs.x).powf(2.)+(self.y-rhs.y).powf(2.)).sqrt()}pub fn dot(&self,rhs:Point2f)->f64{self.x*rhs.x+self.y*rhs.y}pub fn cross(&self,rhs:Point2f)->f64{self.x*rhs.y-self.y*rhs.x}pub fn is_orthogonal(&self,rhs:Point2f)->bool{self.dot(rhs).abs()<EPS}pub fn is_parallel(&self,rhs:Point2f)->bool{self.cross(rhs).abs()<EPS}pub fn rotate(&self,center:Point2f,angle:Radian)->Point2f{Point2f{x:self.x*angle.0.cos()-self.y*angle.0.sin()+center.x-center.x*angle.0.cos()+center.y*angle.0.sin(),y:self.x*angle.0.sin()+self.y*angle.0.cos()+center.y-center.x*angle.0.sin()-center.y*angle.0.cos(),}}}}pub mod prelude{pub const EPS:f64=1e-10;#[macro_export]macro_rules!__cargo_equip_macro_def_procon_library_rs_assert_float{($left:expr,$right:expr)=>{match(&$left,&$right){(left_val,right_val)=>{if!((*left_val-*right_val).abs()<EPS){panic!("assertion failed: `(left == right)` (left: `{:?}`, right: `{:?})`",left_val,right_val);}}}};}macro_rules!assert_float{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_procon_library_rs_assert_float!{$($tt)*})}}}pub mod input{pub fn input_value<T>()->T where T:std::str::FromStr,<T as std::str::FromStr>::Err:std::fmt::Debug,{let stdin=std::io::stdin();let mut buf=String::new();stdin.read_line(&mut buf).unwrap();buf=buf.trim_end().to_owned();let n=buf.parse().unwrap();n}pub fn input_tuple_2<T>()->(T,T)where T:std::str::FromStr,<T as std::str::FromStr>::Err:std::fmt::Debug,{let stdin=std::io::stdin();let mut buf=String::new();stdin.read_line(&mut buf).unwrap();buf=buf.trim_end().to_owned();let mut iter=buf.split_whitespace();let n=iter.next().unwrap().parse().unwrap();let m=iter.next().unwrap().parse().unwrap();(n,m)}pub fn input_vec<T>()->Vec<T>where T:std::str::FromStr,<T as std::str::FromStr>::Err:std::fmt::Debug,{let stdin=std::io::stdin();let mut buf=String::new();stdin.read_line(&mut buf).unwrap();buf=buf.trim_end().to_owned();let iter=buf.split_whitespace();let line=iter.map(|x|x.parse().unwrap()).collect();line}pub fn input_vec_2d<T>(n:usize)->Vec<Vec<T>>where T:std::str::FromStr,<T as std::str::FromStr>::Err:std::fmt::Debug,{let stdin=std::io::stdin();let mut a=Vec::with_capacity(n);for _ in 0..n{let mut buf=String::new();stdin.read_line(&mut buf).unwrap();buf=buf.trim_end().to_owned();let iter=buf.split_whitespace();let line=iter.map(|x|x.parse().unwrap()).collect();a.push(line);}a}pub fn input_tuple_2_vec<T>(n:usize)->Vec<(T,T)>where T:std::str::FromStr,<T as std::str::FromStr>::Err:std::fmt::Debug,{let stdin=std::io::stdin();let mut s_t=Vec::with_capacity(n);for _ in 0..n{let mut buf=String::new();stdin.read_line(&mut buf).unwrap();buf=buf.trim_end().to_owned();let mut iter=buf.split_whitespace();let s=iter.next().unwrap().parse().unwrap();let t=iter.next().unwrap().parse().unwrap();s_t.push((s,t));}s_t}pub fn input_tuple_3_vec<T>(n:usize)->Vec<(T,T,T)>where T:std::str::FromStr,<T as std::str::FromStr>::Err:std::fmt::Debug,{let stdin=std::io::stdin();let mut s_t_d=Vec::with_capacity(n);for _ in 0..n{let mut buf=String::new();stdin.read_line(&mut buf).unwrap();buf=buf.trim_end().to_owned();let mut iter=buf.split_whitespace();let s=iter.next().unwrap().parse().unwrap();let t=iter.next().unwrap().parse().unwrap();let d=iter.next().unwrap().parse().unwrap();s_t_d.push((s,t,d));}s_t_d}pub fn input_char_vec()->Vec<char>{let stdin=std::io::stdin();let mut buf=String::new();stdin.read_line(&mut buf).unwrap();buf=buf.trim_end().to_owned();let x=buf.chars().collect();x}}pub mod math{pub fn to_n_adic(x:isize,radix:isize)->Vec<usize>{if x==0{return vec![0];}let mut x=x;let mut list=Vec::new();while x!=0{let mut p=x/radix;let mut q=x%radix;if q<0{p+=1;q+=-radix;}list.push(q as usize);x=p;}list.reverse();list}}pub mod modulus{pub const PRIME_1_000_000_007:usize=1_000_000_007;pub const PRIME_998_244_353:usize=998_244_353;pub fn mod_pow(a:usize,n:usize,p:usize)->usize{if n==0{return 1%p;}if n==1{return a%p;}if n%2==1{return(a*mod_pow(a,n-1,p))%p;}let t=mod_pow(a,n/2,p);return(t*t)%p;}pub fn mod_inv(a:usize,p:usize)->usize{return mod_pow(a,p-2,p);}pub fn mod_perm(n:usize,k:usize,p:usize)->usize{let mut ret=1;for i in 0..k{ret=(ret*(n-i))%p;}return ret;}pub fn mod_comb(n:usize,k:usize,p:usize)->usize{let a=mod_perm(n,k,p);let b=mod_perm(k,k,p);return(a*mod_inv(b,p))%p;}pub fn mod_comb_with_repetition(n:usize,k:usize,p:usize)->usize{mod_comb(n-1+k,n-1,p)}pub fn mod_perm_with_repetition(n:usize,k:usize,p:usize)->usize{mod_pow(n,k,p)}}pub mod prime{pub fn get_prime(n:usize)->Vec<usize>{assert!(n>=2,"n must be 2 or more");let mut is_prime=vec![true;n+1];let mut list=Vec::with_capacity(n);is_prime[0]=false;is_prime[1]=false;for i in 2..=n{if is_prime[i]{list.push(i);for j in(i*2..=n).step_by(i){is_prime[j]=false;}}}list}pub fn is_prime(x:usize)->bool{if x==2{return true;}if x<2||x%2==0{return false;}let mut i=3;while i*i<=x{if x%i==0{return false;}i=i+2;}true}pub fn prime_factorize(n:usize)->Vec<usize>{let mut current=n;let mut list=Vec::new();{let mut i=2;while i*i<=n{while current%i==0{list.push(i);current/=i;}if current==1{break;}i+=1;}if current!=1{list.push(current);}}list}pub fn pre_osa_k(n:usize)->Vec<usize>{let mut min_factor:Vec<_> =(0..=n).collect();let mut i=2;while i*i<=n{if min_factor[i]==i{for k in(i*2..=n).step_by(i){if min_factor[k]>i{min_factor[k]=i;}}}i+=1;}min_factor}pub fn osa_k(m:usize,min_factor:&Vec<usize>)->Vec<usize>{let mut k=m;let mut primes=Vec::new();while k>=2{primes.push(min_factor[k]);k/=min_factor[k];}primes}pub fn divisors(n:usize)->Vec<usize>{let mut list=Vec::new();{let mut i=1;while i*i<=n{if n%i==0{list.push(i);if n/i!=i{list.push(n/i);}}i+=1;}}list.sort();list}}pub mod run_length_encoding{pub fn run_length_encoding<T>(list:&Vec<T>)->Vec<(T,usize)>where T:PartialEq+Copy,{let mut result=Vec::new();for&value in list.iter(){if let Some((next,size))=result.pop(){if next==value{result.push((next,size+1));}else{result.push((next,size));result.push((value,1));}}else{result.push((value,1));}}result}}pub mod structure{pub mod linked_list{use super::linked_list::LinkedList::*;#[derive(Debug,Clone)]pub enum LinkedList{Cons(usize,Box<LinkedList>),Nil,}impl LinkedList{pub fn new()->LinkedList{Nil}pub fn prepend(self,element:usize)->LinkedList{Cons(element,Box::new(self))}pub fn len(&self)->usize{match&self{Cons(_,ref tail)=>1+tail.len(),Self::Nil=>0,}}pub fn stringify(&self)->String{match&self{Cons(head,ref tail)=>format!("{}, {}",head,tail.stringify()),Self::Nil=>format!("Nil"),}}}}pub mod persistent_array{use std::rc::Rc;#[derive(Debug,Clone)]pub enum PersistentArray{Cons(usize,Vec<Rc<PersistentArray>>),Nil,}impl PersistentArray{pub fn new()->Rc<PersistentArray>{Rc::new(PersistentArray::Nil)}pub fn set(&self,index:usize,value:usize)->Rc<PersistentArray>{let(mut new_value,mut new_children)=match self{Self::Cons(prev_value,prev_children)=>(*prev_value,prev_children.clone()),Self::Nil=>(0,vec![Rc::new(PersistentArray::Nil);20]),};if index==0{new_value=value;}else{new_children[index%20]=new_children[index%20].set(index/20,value);}Rc::new(PersistentArray::Cons(new_value,new_children))}pub fn get(&self,index:usize)->usize{match self{Self::Cons(value,children)=>{if index==0{*value}else{children[index%20].get(index/20)}}Self::Nil=>0,}}}}pub mod persistent_stack{use std::rc::Rc;#[derive(Debug,Clone)]pub enum PersistentStack{Cons(usize,Rc<PersistentStack>),Nil,}impl PersistentStack{pub fn new()->PersistentStack{PersistentStack::Nil}pub fn top(&self)->Option<usize>{match self{Self::Cons(value,_prev)=>Some(*value),Self::Nil=>None,}}pub fn push(self:&Rc<PersistentStack>,x:usize)->Rc<PersistentStack>{Rc::new(PersistentStack::Cons(x,Rc::clone(self)))}pub fn pop(&self)->Option<Rc<PersistentStack>>{match self{Self::Cons(_value,prev)=>Some(Rc::clone(prev)),Self::Nil=>None,}}}}}pub fn gcd(mut n:u64,mut m:u64)->u64{while m!=0{if m<n{let t=m;m=n;n=t;}m=m%n;}n}}
    }

    pub(crate) mod macros {
        pub mod procon_library_rs {pub use crate::__cargo_equip_macro_def_procon_library_rs_assert_float as assert_float;}
    }

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

    mod preludes {
        pub mod procon_library_rs {}
    }
}