#979260 (Rust) No.2677 Minmax Independent Set

• 問題: No.2677 Minmax Independent Set
• ユーザー: 37kt
• 提出日時: 2024-05-06 09:30:32
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 131 ms / 2,000 ms
• コード長: 12,004 bytes
• コンパイル時間: 18,681 ms
• コンパイル使用メモリ: 384,088 KB
• 実行使用メモリ: 34,916 KB
• 最終ジャッジ日時: 2024-05-06 09:31:00
• 合計ジャッジ時間: 20,253 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	131 ms; 27,996 KB
testcase_06	AC	129 ms; 27,764 KB
testcase_07	AC	107 ms; 27,864 KB
testcase_08	AC	128 ms; 27,996 KB
testcase_09	AC	106 ms; 27,996 KB
testcase_10	AC	94 ms; 33,904 KB
testcase_11	AC	101 ms; 34,080 KB
testcase_12	AC	68 ms; 27,932 KB
testcase_13	AC	118 ms; 32,664 KB
testcase_14	AC	107 ms; 33,060 KB
testcase_15	AC	106 ms; 31,504 KB
testcase_16	AC	113 ms; 27,640 KB
testcase_17	AC	107 ms; 27,888 KB
testcase_18	AC	62 ms; 18,380 KB
testcase_19	AC	82 ms; 21,472 KB
testcase_20	AC	23 ms; 8,696 KB
testcase_21	AC	83 ms; 23,488 KB
testcase_22	AC	6 ms; 5,376 KB
testcase_23	AC	1 ms; 5,376 KB
testcase_24	AC	1 ms; 5,376 KB
testcase_25	AC	1 ms; 5,376 KB
testcase_26	AC	1 ms; 5,376 KB
testcase_27	AC	1 ms; 5,376 KB
testcase_28	AC	93 ms; 34,916 KB
testcase_29	AC	111 ms; 27,876 KB
testcase_30	AC	1 ms; 5,376 KB
testcase_31	AC	1 ms; 5,376 KB
testcase_32	AC	1 ms; 5,376 KB
testcase_33	AC	1 ms; 5,376 KB
testcase_34	AC	1 ms; 5,376 KB
testcase_35	AC	1 ms; 5,376 KB
testcase_36	AC	1 ms; 5,376 KB
testcase_37	AC	1 ms; 5,376 KB
testcase_38	AC	1 ms; 5,376 KB
testcase_39	AC	1 ms; 5,376 KB
testcase_40	AC	2 ms; 5,376 KB
testcase_41	AC	3 ms; 5,376 KB
testcase_42	AC	5 ms; 5,376 KB
testcase_43	AC	10 ms; 5,376 KB
testcase_44	AC	20 ms; 8,176 KB
testcase_45	AC	42 ms; 14,508 KB
testcase_46	AC	105 ms; 27,500 KB
testcase_47	AC	108 ms; 27,992 KB
testcase_48	AC	106 ms; 27,868 KB
testcase_49	AC	108 ms; 28,000 KB
testcase_50	AC	30 ms; 14,692 KB
testcase_51	AC	3 ms; 5,376 KB
testcase_52	AC	74 ms; 29,700 KB
testcase_53	AC	69 ms; 27,808 KB
testcase_54	AC	2 ms; 5,376 KB
testcase_55	AC	89 ms; 31,820 KB
testcase_56	AC	90 ms; 33,220 KB
testcase_57	AC	87 ms; 31,772 KB
testcase_58	AC	93 ms; 31,804 KB
testcase_59	AC	91 ms; 33,216 KB
testcase_60	AC	60 ms; 29,152 KB
testcase_61	AC	58 ms; 27,908 KB
testcase_62	AC	55 ms; 27,924 KB
testcase_63	AC	56 ms; 27,688 KB

ソースコード

pub use __cargo_equip::prelude::*;

use algebraic::{act, algebra, monoid};
use chminmax::chmin;
use graph::Graph;
#[allow(unused_imports)]
use proconio::{
    input,
    marker::{Bytes, Chars, Usize1},
};
use re_rooting_dp::ReRootingDP;

type T = [usize; 2];

algebra!(M, T);
monoid!(M, [0, 0], |&[a, b]: &T, &[c, d]: &T| [
    a + c,
    a.max(b) + c.max(d)
]);

algebra!(V, ());
act!(V, T, |_, &[a, b]: &T| [b, a + 1]);

algebra!(E, ());
act!(E, T, |_, &x| x);

fn main() {
    input! {
        n: usize,
        uv: [(Usize1, Usize1); n - 1],
    }
    let g = Graph::from_unweighted_undirected_edges(n, &uv);
    let dp = ReRootingDP::build::<M, V, E>(&g);
    let mut res = 1 << 40;
    for i in 0..n {
        chmin!(res, dp.prod(i)[1]);
    }
    println!("{}", res);
}

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

///  # Bundled libraries
/// 
///  - `algebraic 0.1.0 (path+████████████████████████████████████████████████████████)`    published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::algebraic`
///  - `chminmax 0.1.0 (path+████████████████████████████████████████████████████)`         published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::chminmax`
///  - `graph 0.1.0 (path+████████████████████████████████████████████████)`                published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::graph`
///  - `re-rooting-dp 0.1.0 (path+███████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::re_rooting_dp`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod algebraic {pub use crate::__cargo_equip::macros::algebraic::*;pub trait Algebra{type S;}pub trait Act:Algebra{type X;fn act(f:&Self::S,x:&Self::X)->Self::X;}pub trait Monoid:Algebra{fn e()->Self::S;fn op(x:&Self::S,y:&Self::S)->Self::S;}pub trait Group:Monoid{fn inv(x:&Self::S)->Self::S;}pub trait Zero{fn zero()->Self;fn is_zero(&self)->bool;}pub trait One{fn one()->Self;fn is_one(&self)->bool;}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_algebra{($ident:ident,$ty:ty)=>{#[derive(Clone)]enum$ident{}impl$crate::__cargo_equip::crates::algebraic::Algebra for$ident{type S=$ty;}};}macro_rules!algebra{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_algebra!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_act{($ident:ident,$tar:ty,$act:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Act for$ident{type X=$tar;#[inline]fn act(f:&Self::S,x:&Self::X)->Self::X{$act(f,x)}}};}macro_rules!act{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_act!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_monoid{($ident:ident,$e:expr,$op:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}};}macro_rules!monoid{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_monoid!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_group{($ident:ident,$e:expr,$op:expr,$inv:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}impl$crate::__cargo_equip::crates::algebraic::Group for$ident{#[inline]fn inv(x:&Self::S)->Self::S{$inv(x)}}};}macro_rules!group{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_group!{$($tt)*})}macro_rules!impl_zero_one{($($t:ty)*)=>{$(impl$crate::__cargo_equip::crates::algebraic::Zero for$t{fn zero()->Self{0}fn is_zero(&self)->bool{*self==0}}impl$crate::__cargo_equip::crates::algebraic::One for$t{fn one()->Self{1}fn is_one(&self)->bool{*self==1}})*};}impl_zero_one!(usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128);}
        pub mod chminmax {pub use crate::__cargo_equip::macros::chminmax::*;#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_min{($a:expr$(,)*)=>{{$a}};($a:expr,$b:expr$(,)*)=>{{std::cmp::min($a,$b)}};($a:expr,$($rest:expr),+$(,)*)=>{{std::cmp::min($a,$crate::__cargo_equip::crates::chminmax::min!($($rest),+))}};}macro_rules!min{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_min!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_max{($a:expr$(,)*)=>{{$a}};($a:expr,$b:expr$(,)*)=>{{std::cmp::max($a,$b)}};($a:expr,$($rest:expr),+$(,)*)=>{{std::cmp::max($a,$crate::__cargo_equip::crates::chminmax::max!($($rest),+))}};}macro_rules!max{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_max!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_chmin{($base:expr,$($cmps:expr),+$(,)*)=>{{let cmp_min=$crate::__cargo_equip::crates::chminmax::min!($($cmps),+);if$base>cmp_min{$base=cmp_min;true}else{false}}};}macro_rules!chmin{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_chmin!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_chmax{($base:expr,$($cmps:expr),+$(,)*)=>{{let cmp_max=$crate::__cargo_equip::crates::chminmax::max!($($cmps),+);if$base<cmp_max{$base=cmp_max;true}else{false}}};}macro_rules!chmax{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_chmax!{$($tt)*})}}
        pub mod graph {use std::ops::Index;#[derive(Clone)]pub struct Graph<V,E>where V:Clone,E:Clone,{vertices:Vec<V>,edges:Vec<(usize,E)>,pos:Vec<usize>,edge_id:Vec<usize>,edges_count:usize,}pub const GRID_NEIGHBOURS_4:&[(usize,usize)]=&[(!0,0),(0,!0),(1,0),(0,1)];pub const GRID_NEIGHBOURS_8:&[(usize,usize)]=&[(!0,0),(0,!0),(1,0),(0,1),(!0,!0),(!0,1),(1,!0),(1,1),];impl<V,E>Graph<V,E>where V:Clone,E:Clone,{pub fn from_vertices_and_directed_edges(vertices:&[V],edges:&[(usize,usize,E)])->Self{if edges.is_empty(){return Self{vertices:vertices.to_vec(),edges:vec![],pos:vec![0;vertices.len()+1],edge_id:vec![],edges_count:0,};}let n=vertices.len();let mut pos=vec![0;n+1];for&(u,_,_)in edges{pos[u]+=1;}for i in 1..=n{pos[i]+=pos[i-1];}let mut ord=vec![0;edges.len()];for i in(0..edges.len()).rev(){let u=edges[i].0;pos[u]-=1;ord[pos[u]]=i;}Self{vertices:vertices.to_vec(),edge_id:ord.clone(),edges:ord.into_iter().map(|i|(edges[i].1,edges[i].2.clone())).collect(),pos,edges_count:edges.len(),}}pub fn from_vertices_and_undirected_edges(vertices:&[V],edges:&[(usize,usize,E)])->Self{if edges.is_empty(){return Self{vertices:vertices.to_vec(),edges:vec![],pos:vec![0;vertices.len()+1],edge_id:vec![],edges_count:0,};}let n=vertices.len();let mut pos=vec![0;n+1];for&(u,v,_)in edges{pos[u]+=1;pos[v]+=1;}for i in 1..=n{pos[i]+=pos[i-1];}let mut ord=vec![0;edges.len()*2];for i in(0..edges.len()*2).rev(){if i&1==0{let u=edges[i>>1].0;pos[u]-=1;ord[pos[u]]=i;}else{let v=edges[i>>1].1;pos[v]-=1;ord[pos[v]]=i;}}Self{vertices:vertices.to_vec(),edge_id:ord.iter().map(|&i|i/2).collect(),edges:ord.into_iter().map(|i|{(if i&1==0{edges[i>>1].1}else{edges[i>>1].0},edges[i>>1].2.clone(),)}).collect(),pos,edges_count:edges.len(),}}pub fn len(&self)->usize{self.vertices.len()}pub fn edges_count(&self)->usize{self.edges_count}pub fn vertex(&self,v:usize)->&V{&self.vertices[v]}pub fn edges(&self,v:usize)->&[(usize,E)]{let l=self.pos[v];let r=self.pos[v+1];&self.edges[l..r]}pub fn edge_id(&self,v:usize,i:usize)->usize{self.edge_id[self.pos[v]+i]}pub fn from_grid(grid:&Vec<Vec<V>>,neighbours:&[(usize,usize)],cost:impl Fn(&V,&V)->Option<E>,)->Self{let h=grid.len();let w=grid[0].len();let mut edges=vec![];for i in 0..h{for j in 0..w{for&(di,dj)in neighbours{let ni=i.wrapping_add(di);let nj=j.wrapping_add(dj);if ni>=h||nj>=w{continue;}if let Some(c)=cost(&grid[i][j],&grid[ni][nj]){edges.push((i*w+j,ni*w+nj,c));}}}}Self::from_vertices_and_directed_edges(&grid.into_iter().flatten().cloned().collect::<Vec<_>>(),&edges,)}}impl<V,E>Index<usize>for Graph<V,E>where V:Clone,E:Clone,{type Output=[(usize,E)];fn index(&self,v:usize)->&[(usize,E)]{self.edges(v)}}impl<E>Graph<(),E>where E:Clone,{pub fn from_directed_edges(n:usize,edges:&[(usize,usize,E)])->Self{Self::from_vertices_and_directed_edges(&vec![();n],edges)}pub fn from_undirected_edges(n:usize,edges:&[(usize,usize,E)])->Self{Self::from_vertices_and_undirected_edges(&vec![();n],edges)}}impl<V>Graph<V,()>where V:Clone,{pub fn from_vertices_and_unweighted_directed_edges(vertices:&[V],edges:&[(usize,usize)],)->Self{Self::from_vertices_and_directed_edges(vertices,&edges.iter().map(|&(u,v)|(u,v,())).collect::<Vec<_>>(),)}pub fn from_vertices_and_unweighted_undirected_edges(vertices:&[V],edges:&[(usize,usize)],)->Self{Self::from_vertices_and_undirected_edges(vertices,&edges.iter().map(|&(u,v)|(u,v,())).collect::<Vec<_>>(),)}}impl Graph<(),()>{pub fn from_unweighted_directed_edges(n:usize,edges:&[(usize,usize)])->Self{Self::from_directed_edges(n,&edges.iter().map(|&(u,v)|(u,v,())).collect::<Vec<_>>(),)}pub fn from_unweighted_undirected_edges(n:usize,edges:&[(usize,usize)])->Self{Self::from_undirected_edges(n,&edges.iter().map(|&(u,v)|(u,v,())).collect::<Vec<_>>(),)}}}
        pub mod re_rooting_dp {use crate::__cargo_equip::preludes::re_rooting_dp::*;use algebraic::{Act,Monoid};use graph::Graph;pub struct ReRootingDP<S>where S:Clone,{par:Vec<usize>,dp:Vec<S>,dpl:Vec<S>,dph:Vec<S>,}impl<T>ReRootingDP<T>where T:Clone,{pub fn build<M,V,E>(g:&Graph<V::S,E::S>)->Self where M:Monoid<S=T>,M::S:Clone,V:Act<X=M::S>,V::S:Clone,E:Act<X=M::S>,E::S:Clone,{let n=g.len();let mut ord=vec![];let mut par=vec![!0;n];let mut st=vec![0];while let Some(v)=st.pop(){ord.push(v);for&(u,_)in&g[v]{if u!=0&&par[u]==!0{par[u]=v;st.push(u);}}}let mut dpl=vec![M::e();n];let mut dph=vec![M::e();n];let mut dp=vec![M::e();n];for&v in ord.iter().rev(){let m=g[v].len();let mut xl=vec![M::e();m+1];let mut xr=vec![M::e();m+1];for i in 0..m{let(u,_)=g[v][i];if u==par[v]{xl[i+1]=xl[i].clone();}else{xl[i+1]=M::op(&xl[i],&dph[u]);}}for i in(0..m).rev(){let(u,_)=g[v][i];if u==par[v]{xr[i]=xr[i+1].clone();}else{xr[i]=M::op(&dph[u],&xr[i+1]);}}for i in 0..m{let(u,_)=g[v][i];if u!=par[v]{dph[u]=M::op(&xl[i],&xr[i+1]);}}dp[v]=xr[0].clone();dpl[v]=V::act(&g.vertex(v),&dp[v]);for(u,w)in&g[v]{if*u==par[v]{dph[v]=E::act(&w,&dpl[v]);}}}dp[0]=V::act(&g.vertex(0),&dp[0]);for&(u,_)in&g[0]{dph[u]=V::act(&g.vertex(0),&dph[u]);}for&v in&ord{for(u,w)in&g[v]{if*u==par[v]{continue;}let mut x=E::act(&w,&dph[*u]);for&(vv,_)in&g[*u]{if vv==v{continue;}dph[vv]=M::op(&dph[vv],&x);dph[vv]=V::act(&g.vertex(*u),&dph[vv]);}x=M::op(&dp[*u],&x);dp[*u]=V::act(&g.vertex(*u),&x);}}Self{par,dp,dpl,dph}}pub fn prod(&self,v:usize)->T{self.dp[v].clone()}pub fn prod_subtree(&self,v:usize,p:usize)->T{if p==!0{self.dp[v].clone()}else if self.par[v]==p{self.dpl[v].clone()}else{self.dph[p].clone()}}pub fn par(&self,v:usize)->usize{self.par[v]}}}
    }

    pub(crate) mod macros {
        pub mod algebraic {pub use crate::{__cargo_equip_macro_def_algebraic_act as act,__cargo_equip_macro_def_algebraic_algebra as algebra,__cargo_equip_macro_def_algebraic_group as group,__cargo_equip_macro_def_algebraic_monoid as monoid};}
        pub mod chminmax {pub use crate::{__cargo_equip_macro_def_chminmax_chmax as chmax,__cargo_equip_macro_def_chminmax_chmin as chmin,__cargo_equip_macro_def_chminmax_max as max,__cargo_equip_macro_def_chminmax_min as min};}
        pub mod graph {}
        pub mod re_rooting_dp {}
    }

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

    mod preludes {
        pub mod algebraic {}
        pub mod chminmax {}
        pub mod graph {}
        pub mod re_rooting_dp {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{algebraic,graph};}
    }
}