結果

問題 No.1917 LCMST
ユーザー rhoo
提出日時 2025-07-16 13:49:54
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 518 ms / 4,000 ms
コード長 3,875 bytes
コンパイル時間 12,596 ms
コンパイル使用メモリ 400,272 KB
実行使用メモリ 76,800 KB
最終ジャッジ日時 2025-07-16 13:50:30
合計ジャッジ時間 25,826 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `n`
   --> src/main.rs:116:12
    |
116 |     fn new(n:usize)->E{
    |            ^ help: if this is intentional, prefix it with an underscore: `_n`
    |
    = note: `#[warn(unused_variables)]` on by default

ソースコード

diff # 

#![allow(unused_imports,non_snake_case,dead_code)]
use std::{cmp::Reverse as Rev,ops::Range,collections::*,iter::*};
use proconio::{marker::*,*};



// LCMST



#[fastout]
fn main(){
    input!{
        n:usize,
        mut a:[usize;n],
    }
    a.sort_unstable();
    let mut ans=0;
    a.dedup_by(|a,b|a==b && {ans+=*a; true});
    let n=a.len();
    let maxA=1e6 as usize+5;

    let e=E::new(maxA);
    let divs=(0..n).map(|i|e.divisor(a[i])).collect::<Vec<_>>();
    let mut id_to_div=divs.iter().flatten().copied().collect::<Vec<_>>();
    id_to_div.sort_unstable();
    id_to_div.dedup();

    let mut div_to_id=vec![!0;maxA];
    for i in 0..id_to_div.len(){
        div_to_id[id_to_div[i]]=i;
    }

    let ds=id_to_div.len();
    let mut que=vec![!0;ds];
    let mut co_que=vec![vec![];ds];
    let mut seen=vec![false;n];

    for i in (1..n).rev(){
        for &d in &divs[i]{
            let id=div_to_id[d];
            co_que[id].push(i);
        }
    }

    seen[0]=true;
    let mut min=BTreeSet::new();
    for &d in &divs[0]{
        let id=div_to_id[d];
        que[id]=que[id].min(a[0]);
        if !co_que[id].is_empty(){
            let m0=que[id];
            let m1=a[*co_que[id].last().unwrap()];
            let w=m0/d*m1;
            min.insert((w,id));
        }
    }

    // eprintln!("{:?}",min);
    for _ in 1..n{
        // eprintln!("============= before =============");
        // eprintln!("{:?}",que);
        // eprintln!("{:?}",co_que);
        // eprintln!("{:?}",min);

        let (w,id)=min.first().unwrap();
        ans+=*w as usize;
        let new=*co_que[*id].last().unwrap();
        // eprintln!("{w}: {} {}",que[*id],a[new]);

        seen[new]=true;
        for &d in &divs[new]{
            let id=div_to_id[d] as usize;
            if que[id]!=!0 && !co_que[id].is_empty(){
                let cur=que[id]/d*a[*co_que[id].last().unwrap()];
                let f=min.remove(&(cur,id));
                assert!(f);
            }

            que[id]=que[id].min(a[new]);
            while let Some(&v)=co_que[id].last(){
                if seen[v]{
                    co_que[id].pop().unwrap();
                } else{
                    break;
                }
            }

            if !co_que[id].is_empty(){
                let m0=que[id];
                let m1=a[*co_que[id].last().unwrap()];
                let w=m0/d*m1;
                min.insert((w,id));
            }
        }

        // eprintln!();
        // eprintln!("============= after =============");
        // eprintln!("{:?}",que);
        // eprintln!("{:?}",co_que);
        // eprintln!("{:?}",min);
        // eprintln!();
        // eprintln!();
        // eprintln!();
    }

    println!("{ans}");
}



struct E{
    a:Vec<usize>,
}
impl E{
    fn new(n:usize)->E{
        let mut a=vec![!0;1e6 as usize+5];
        for i in 2..a.len(){
            if a[i]!=!0{
                continue;
            }
            for j in 1..{
                if a.len()<=i*j{
                    break;
                }
                a[i*j]=i;
            }
        }
        E{a}
    }

    fn divisor(&self,mut n:usize)->Vec<usize>{
        let mut ps=vec![];
        while self.a[n]!=!0{
            let p=self.a[n];
            let mut cnt=0;
            while n%p==0{
                cnt+=1;
                n/=p;
            }
            ps.push((p,cnt));
        }

        if n!=1{
            ps.push((n,1));
        }

        fn rec(ps:&[(usize,usize)],i:usize,mut div:usize,divs:&mut Vec<usize>){
            if i==!0{
                divs.push(div);
                return;
            }
            let (p,cnt)=ps[i];
            for _ in 0..=cnt{
                rec(ps,i-1,div,divs);
                div*=p;
            }
        }

        let mut divs=vec![];
        rec(&ps,ps.len()-1,1,&mut divs);
        divs
    }
}
0