#979260 (Rust) No.2677 Minmax Independent Set

提出ソース
結果

問題	No.2677 Minmax Independent Set
ユーザー	37kt
提出日時	2024-05-06 09:30:32
言語	Rust (1.83.0 + proconio)
結果	AC
実行時間	127 ms / 2,000 ms
コード長	12,004 bytes
コンパイル時間	14,118 ms
コンパイル使用メモリ	404,280 KB
実行使用メモリ	34,740 KB
最終ジャッジ日時	2024-11-28 15:05:34
合計ジャッジ時間	21,965 ms
ジャッジサーバーID （参考情報）	judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 61
権限があれば一括ダウンロードができます
ソースコード

raw source code
プレゼンテーションモードにする

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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};}
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
yukicoder

結果

ソースコード
