#978523 (Rust) No.901 K-ary εxtrεεmε

提出ソース
結果

問題	No.901 K-ary εxtrεεmε
ユーザー	37kt
提出日時	2024-05-02 11:09:39
言語	Rust (1.77.0 + proconio)
結果	WA
実行時間	-
コード長	15,560 bytes
コンパイル時間	23,563 ms
コンパイル使用メモリ	377,036 KB
実行使用メモリ	41,384 KB
最終ジャッジ日時	2024-11-23 00:29:33
合計ジャッジ時間	26,515 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	133 ms 41,384 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	419 ms 36,492 KB
testcase_28	AC	422 ms 36,620 KB
testcase_29	AC	424 ms 36,496 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
pub use __cargo_equip::prelude::*;

use graph::Graph;
#[allow(unused_imports)]
use proconio::{
    input,
    marker::{Bytes, Chars, Usize1},
};
use static_top_tree_dp::{StaticTopTreeDP, TreeDPOperator};

enum Op {}
impl TreeDPOperator for Op {
    type V = bool;
    type E = i64;
    type Path = Result<(i64, i64, i64, i64), i64>;
    type Point = Option<(i64, i64)>;

    fn vertex(&v: &Self::V) -> Self::Path {
        if v {
            Ok((0, 0, 0, 0))
        } else {
            Err(0)
        }
    }

    fn add_vertex(&d: &Self::Point, &v: &Self::V) -> Self::Path {
        match (d, v) {
            (Some((s, d)), true) => Ok((s + d, 0, 0, 0)),
            (Some((s, d)), false) => Ok((s, d, 0, 0)),
            (None, true) => Ok((0, 0, 0, 0)),
            (None, false) => Err(0),
        }
    }

    fn add_edge(&d: &Self::Path, &e: &Self::E) -> Self::Point {
        if let Ok((s, d, _, _)) = d {
            Some((s, d + e))
        } else {
            None
        }
    }

    fn rake(&l: &Self::Point, &r: &Self::Point) -> Self::Point {
        match (l, r) {
            (Some((ls, ld)), Some((rs, rd))) => Some((ls + rs, ld + rd)),
            (Some((ls, ld)), None) => Some((ls, ld)),
            (None, Some((rs, rd))) => Some((rs, rd)),
            (None, None) => None,
        }
    }
    fn compress(&p: &Self::Path, &c: &Self::Path, &e: &Self::E) -> Self::Path {
        match (p, c) {
            (Ok((ps, pa, pb, pc)), Ok((cs, ca, cb, cc))) => {
                Ok((ps + cs + e + pa + pb + ca + cc, 0, cb, pc))
            }
            (Ok((ps, pa, pb, pc)), Err(ch)) => Ok((ps, pa, pb + ch + e, pc)),
            (Err(ph), Ok((cs, ca, cb, cc))) => Ok((cs, ca, cb, cc + ph + e)),
            (Err(ph), Err(ch)) => Err(ph + ch + e),
        }
    }
}

fn main() {
    input! {
        n: usize,
        uvw: [(usize, usize, i64); n - 1],
        q: usize,
    }
    let g = Graph::from_vertices_and_undirected_edges(&vec![false; n], &uvw);
    let mut stt = StaticTopTreeDP::<Op>::new(&g);
    for _ in 0..q {
        input! {
            x: [usize],
        }
        for &x in &x {
            stt.set_vertex(x, true);
        }
        let res = stt.prod().unwrap().0;
        println!("{}", res);
        for &x in &x {
            stt.set_vertex(x, false);
        }
    }
}

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

///  # Bundled libraries
/// 
///  - `graph 0.1.0 (path+████████████████████████████████████████████████)`                                                  published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::graph`
///  - `heavy-light-decomposition 0.1.0 (path+█████████████████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::heavy_light_decomposition`
///  - `static-top-tree-dp 0.1.0 (path+████████████████████████████████████████████████████████████)`                         published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::static_top_tree_dp`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        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 heavy_light_decomposition {use crate::__cargo_equip::preludes::heavy_light_decomposition::*;use graph::Graph;use std::mem::swap;pub struct HeavyLightDecomposition{pub t_in:Vec<usize>,pub t_out:Vec<usize>,pub ord:Vec<usize>,pub size:Vec<usize>,pub heavy:Vec<usize>,pub head:Vec<usize>,pub par:Vec<usize>,pub depth:Vec<usize>,}impl HeavyLightDecomposition{pub fn new<V,E>(g:&Graph<V,E>)->Self where V:Clone,E:Clone,{let n=g.len();let mut hld=HeavyLightDecomposition{t_in:vec![0;n],t_out:vec![0;n],ord:vec![],size:vec![0;n],heavy:vec![!0;n],head:vec![0;n],par:vec![!0;n],depth:vec![0;n],};hld.dfs_sz(g,0);hld.dfs_hld(g,0,&mut 0);hld}fn dfs_sz<V,E>(&mut self,g:&Graph<V,E>,v:usize)where V:Clone,E:Clone,{self.size[v]=1;for&(u,_)in&g[v]{if u==self.par[v]{continue;}self.par[u]=v;self.depth[u]=self.depth[v]+1;self.dfs_sz(g,u);self.size[v]+=self.size[u];if self.heavy[v]==!0||self.size[u]>self.size[self.heavy[v]]{self.heavy[v]=u;}}}fn dfs_hld<V,E>(&mut self,g:&Graph<V,E>,v:usize,t:&mut usize)where V:Clone,E:Clone,{self.t_in[v]=*t;self.ord.push(v);*t+=1;if self.heavy[v]!=!0{let u=self.heavy[v];self.head[u]=self.head[v];self.dfs_hld(g,u,t);}for&(u,_)in&g[v]{if u==self.par[v]{continue;}if u==self.heavy[v]{continue;}self.head[u]=u;self.dfs_hld(g,u,t);}self.t_out[v]=*t;}}impl HeavyLightDecomposition{pub fn kth_ancestor(&self,mut v:usize,mut k:usize)->usize{if self.depth[v]<k{return!0;}loop{let u=self.head[v];if self.t_in[v]-k>=self.t_in[u]{return self.ord[self.t_in[v]-k];}k-=1+self.t_in[v]-self.t_in[u];v=self.par[u];}}pub fn lca(&self,mut u:usize,mut v:usize)->usize{loop{if self.t_in[u]>self.t_in[v]{swap(&mut u,&mut v);}if self.head[u]==self.head[v]{return u;}v=self.par[self.head[v]];}}pub fn dist(&self,u:usize,v:usize)->usize{let l=self.lca(u,v);self.depth[u]+self.depth[v]-self.depth[l]*2}pub fn jump(&self,u:usize,v:usize,k:usize)->usize{if k==0{return u;}let l=self.lca(u,v);let d_lu=self.depth[u]-self.depth[l];let d_lv=self.depth[v]-self.depth[l];if k>d_lu+d_lv{!0}else if k<=d_lu{self.kth_ancestor(u,k)}else{self.kth_ancestor(v,d_lu+d_lv-k)}}pub fn vertex(&self,v:usize)->usize{self.t_in[v]}pub fn edge(&self,u:usize,v:usize)->usize{if self.depth[u]<self.depth[v]{self.t_in[v]}else{self.t_in[u]}}pub fn path(&self,mut u:usize,mut v:usize,edge:bool,)->(Vec<(usize,usize)>,Vec<(usize,usize)>){let mut up=vec![];let mut down=vec![];let e=if edge{1}else{0};while self.head[u]!=self.head[v]{if self.t_in[u]<self.t_in[v]{down.push((self.t_in[self.head[v]],self.t_in[v]+1));v=self.par[self.head[v]];}else{up.push((self.t_in[self.head[u]],self.t_in[u]+1));u=self.par[self.head[u]];}}if self.t_in[u]<self.t_in[v]{down.push((self.t_in[u]+e,self.t_in[v]+1));}else if self.t_in[u]>=self.t_in[v]+e{up.push((self.t_in[v]+e,self.t_in[u]+1));}down.reverse();(up,down)}pub fn subtree(&self,v:usize,edge:bool)->(usize,usize){let e=if edge{1}else{0};(self.t_in[v]+e,self.t_out[v])}}}
        pub mod static_top_tree_dp {use crate::__cargo_equip::preludes::static_top_tree_dp::*;use graph::Graph;use heavy_light_decomposition::HeavyLightDecomposition;#[derive(Clone,Copy)]enum Type{Vertex,Compress,Rake,AddEdge,AddVertex,}pub struct StaticTopTree{stt_root:usize,par:Vec<usize>,lch:Vec<usize>,rch:Vec<usize>,ty:Vec<Type>,edge:Vec<usize>,par_edge:Vec<usize>,child:Vec<usize>,cnt:usize,}impl StaticTopTree{pub fn new<V:Clone,E:Clone>(g:&Graph<V,E>)->Self{let n=g.len();let mut s=Self{stt_root:!0,par:vec![!0;n*4],lch:vec![!0;n*4],rch:vec![!0;n*4],ty:vec![Type::Vertex;n*4],edge:vec![!0;n*4],par_edge:vec![!0;n],child:vec![!0;n-1],cnt:n,};let hld=HeavyLightDecomposition::new(g);for v in 0..n{for i in 0..g[v].len(){let(u,_)=g[v][i];if hld.depth[v]<hld.depth[u]{s.par_edge[u]=g.edge_id(v,i);s.child[g.edge_id(v,i)]=u;}}}s.stt_root=s.compress(0,g,&hld).0;s}pub fn len(&self)->usize{self.cnt}fn add(&mut self,mut k:usize,l:usize,r:usize,t:Type)->usize{if k==!0{k=self.cnt;self.cnt+=1;}self.par[k]=!0;self.lch[k]=l;self.rch[k]=r;self.ty[k]=t;if l!=!0{self.par[l]=k;}if r!=!0{self.par[r]=k;}k}fn merge(&mut self,a:&[(usize,usize)],t:Type)->(usize,usize){if a.len()==1{return a[0];}let mut u=a.iter().map(|&(_,s)|s).sum::<usize>();let mut m=0;while m<a.len()&&a[m].1<u{u-=u.min(a[m].1*2);m+=1;}let(i,si)=self.merge(&a[..m],t);let(j,sj)=self.merge(&a[m..],t);let res=(self.add(!0,i,j,t),si+sj);match t{Type::Compress=>{self.edge[res.0]=self.par_edge[a[m].0];}_=>(),}res}fn compress<V:Clone,E:Clone>(&mut self,mut i:usize,g:&Graph<V,E>,hld:&HeavyLightDecomposition,)->(usize,usize){let mut chs=vec![self.add_vertex(i,g,hld)];while hld.heavy[i]!=!0{i=hld.heavy[i];chs.push(self.add_vertex(i,g,hld));}self.merge(&chs,Type::Compress)}fn rake<V:Clone,E:Clone>(&mut self,i:usize,g:&Graph<V,E>,hld:&HeavyLightDecomposition,)->(usize,usize){let mut chs=vec![];for&(u,_)in&g[i]{if u==hld.par[i]||u==hld.heavy[i]{continue;}chs.push(self.add_edge(u,g,hld));}if chs.is_empty(){(!0,0)}else{self.merge(&chs,Type::Rake)}}fn add_edge<V:Clone,E:Clone>(&mut self,i:usize,g:&Graph<V,E>,hld:&HeavyLightDecomposition,)->(usize,usize){let(j,sj)=self.compress(i,g,hld);let res=(self.add(!0,j,!0,Type::AddEdge),sj);self.edge[res.0]=self.par_edge[i];res}fn add_vertex<V:Clone,E:Clone>(&mut self,i:usize,g:&Graph<V,E>,hld:&HeavyLightDecomposition,)->(usize,usize){let(j,sj)=self.rake(i,g,hld);(self.add(i,j,!0,if j==!0{Type::Vertex}else{Type::AddVertex},),sj+1,)}}#[derive(Clone)]enum Data<Path,Point>{Path(Path),Point(Point),}impl<Path,Point>Data<Path,Point>{fn unwrap_path(&self)->&Path{match self{Data::Path(p)=>p,_=>panic!(),}}fn unwrap_point(&self)->&Point{match self{Data::Point(p)=>p,_=>panic!(),}}}pub trait TreeDPOperator{type Path:Clone;type Point:Clone;type V:Clone;type E:Clone;fn vertex(v:&Self::V)->Self::Path;fn compress(p:&Self::Path,c:&Self::Path,e:&Self::E)->Self::Path;fn rake(l:&Self::Point,r:&Self::Point)->Self::Point;fn add_edge(d:&Self::Path,e:&Self::E)->Self::Point;fn add_vertex(d:&Self::Point,v:&Self::V)->Self::Path;}pub struct StaticTopTreeDP<O:TreeDPOperator>{stt:StaticTopTree,sum:Vec<Data<O::Path,O::Point>>,vertex:Vec<O::V>,edge:Vec<O::E>,op:std::marker::PhantomData<O>,}impl<O:TreeDPOperator>StaticTopTreeDP<O>{pub fn new(g:&Graph<O::V,O::E>)->Self{let stt=StaticTopTree::new(g);let mut sum=vec![Data::Path(O::vertex(&g.vertex(0)));stt.len()];let vertex=(0..g.len()).map(|v|g.vertex(v).clone()).collect::<Vec<_>>();let mut edge=if g.len()==1{vec![]}else{vec![g[0][0].1.clone();g.len()-1]};for v in 0..g.len(){sum[v]=Data::Path(O::vertex(&g.vertex(v)));for i in 0..g[v].len(){edge[g.edge_id(v,i)]=g[v][i].1.clone();}}let mut s=Self{stt,sum,vertex,edge,op:std::marker::PhantomData,};s.dfs(s.stt.stt_root);s}pub fn prod(&self)->O::Path{self.sum[self.stt.stt_root].unwrap_path().clone()}pub fn set_vertex(&mut self,mut v:usize,x:O::V){self.vertex[v]=x.clone();while v!=!0{self.update(v);v=self.stt.par[v];}}pub fn set_edge(&mut self,e:usize,x:O::E){self.edge[e]=x.clone();let mut v=self.stt.child[e];while v!=!0{self.update(v);v=self.stt.par[v];}}fn dfs(&mut self,v:usize){if self.stt.lch[v]!=!0{self.dfs(self.stt.lch[v]);}if self.stt.rch[v]!=!0{self.dfs(self.stt.rch[v]);}self.update(v);}fn update(&mut self,v:usize){match self.stt.ty[v]{Type::Vertex=>{self.sum[v]=Data::Path(O::vertex(&self.vertex[v]));}Type::Compress=>{self.sum[v]=Data::Path(O::compress(self.sum[self.stt.lch[v]].unwrap_path(),self.sum[self.stt.rch[v]].unwrap_path(),&self.edge[self.stt.edge[v]],));}Type::Rake=>{self.sum[v]=Data::Point(O::rake(self.sum[self.stt.lch[v]].unwrap_point(),self.sum[self.stt.rch[v]].unwrap_point(),));}Type::AddEdge=>{self.sum[v]=Data::Point(O::add_edge(self.sum[self.stt.lch[v]].unwrap_path(),&self.edge[self.stt.edge[v]],));}Type::AddVertex=>{self.sum[v]=Data::Path(O::add_vertex(self.sum[self.stt.lch[v]].unwrap_point(),&self.vertex[v],));}}}}}
    }

    pub(crate) mod macros {
        pub mod graph {}
        pub mod heavy_light_decomposition {}
        pub mod static_top_tree_dp {}
    }

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

    mod preludes {
        pub mod graph {}
        pub mod heavy_light_decomposition {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::graph;}
        pub mod static_top_tree_dp {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{graph,heavy_light_decomposition};}
    }
}
yukicoder

結果

テストケース

ソースコード
