結果

問題 No.2756 GCD Teleporter
ユーザー maguroflymagurofly
提出日時 2024-05-10 23:07:30
言語 Rust
(1.77.0 + proconio)
結果
WA  
実行時間 -
コード長 4,104 bytes
コンパイル時間 15,323 ms
コンパイル使用メモリ 403,064 KB
実行使用メモリ 17,960 KB
最終ジャッジ日時 2024-05-10 23:07:49
合計ジャッジ時間 14,588 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 7 ms
6,944 KB
testcase_05 AC 22 ms
7,580 KB
testcase_06 AC 55 ms
14,096 KB
testcase_07 AC 43 ms
11,956 KB
testcase_08 AC 41 ms
11,432 KB
testcase_09 AC 35 ms
10,468 KB
testcase_10 AC 49 ms
13,100 KB
testcase_11 AC 64 ms
15,304 KB
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 AC 55 ms
14,848 KB
testcase_21 AC 26 ms
8,832 KB
testcase_22 AC 56 ms
14,720 KB
testcase_23 AC 9 ms
6,940 KB
testcase_24 AC 44 ms
12,288 KB
testcase_25 AC 47 ms
13,004 KB
testcase_26 AC 54 ms
14,080 KB
testcase_27 AC 56 ms
14,592 KB
testcase_28 AC 24 ms
9,600 KB
testcase_29 AC 34 ms
12,032 KB
testcase_30 AC 43 ms
14,592 KB
testcase_31 AC 20 ms
8,704 KB
testcase_32 AC 23 ms
11,904 KB
testcase_33 AC 11 ms
7,040 KB
testcase_34 AC 7 ms
6,944 KB
testcase_35 AC 31 ms
12,544 KB
testcase_36 AC 32 ms
12,304 KB
testcase_37 AC 1 ms
6,944 KB
testcase_38 AC 46 ms
13,848 KB
testcase_39 AC 60 ms
17,960 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `N` should have a snake case name
 --> src/main.rs:9:9
  |
9 |         N: usize,
  |         ^ help: convert the identifier to snake case: `n`
  |
  = note: `#[warn(non_snake_case)]` on by default

warning: variable `A` should have a snake case name
  --> src/main.rs:10:9
   |
10 |         A: [usize; N],
   |         ^ help: convert the identifier to snake case: `a`

ソースコード

diff # 

pub use __cargo_equip::prelude::*;

use proconio::input;
use std::collections::*;
use acl_dsu::*;

fn main() {
    input! {
        N: usize,
        A: [usize; N],
    }
    
    let max = *A.iter().max().unwrap();
    let (_, sieve) = linear_sieve(max);
    let mut by_prime_factor = HashMap::new();
    for i in 0 .. N {
        let mut n = A[i];
        while n > 1 {
            let p = sieve[n];
            while n % p == 0 {
                n /= p;
            }
            by_prime_factor.entry(p).or_insert_with(Vec::new).push(i);
        }
    }
    
    let mut dsu = Dsu::new(N);
    for (_, vertices) in &by_prime_factor {
        for i in 1 .. vertices.len() {
            dsu.merge(vertices[0], vertices[i]);
        }
    }
    
    let mut min_prime_factor = vec![200000; N];
    let mut leaders = vec![];
    for v in 0 .. N {
        let r = dsu.leader(v);
        leaders.push(r);
        let p = &mut min_prime_factor[r];
        let p0 = *p;
        let q = sieve[A[v]];
        if q > 1 {
            *p = p0.min(q);
        }
    }
    leaders.sort_by_key(|&v| min_prime_factor[v] );
    leaders.dedup();
    
    // eprintln!("{:?}", leaders);
    // eprintln!("{:?}", min_prime_factor);
    
    let mut ans = 0;
    for i in 1 .. leaders.len() {
        let p = min_prime_factor[leaders[0]];
        let q = min_prime_factor[leaders[i]];
        let pq = p.min(q);
        if 4 < pq {
            ans += 4;
            min_prime_factor[leaders[0]] = 2;
        } else {
            ans += pq;
            min_prime_factor[leaders[0]] = pq;
        }
    }
    
    println!("{}", ans);
}

fn linear_sieve(limit: usize) -> (Vec<usize>, Vec<usize>) {
    let mut primes = vec![];
    let mut table = vec![1; limit + 1];
    for d in 2 ..= limit {
        if table[d] == 1 {
            table[d] = d;
            primes.push(d);
        }
        for &p in &primes {
            if p * d > limit || p > table[d] { break; }
            table[p * d] = p;
        }
    }
    (primes, table)
}
// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `ac-library-rs-parted-dsu 0.1.0 (path+██████████████████████████████████████████████████████████████████████)` published in https://github.com/qryxip/ac-library-rs-parted licensed under `CC0-1.0` as `crate::__cargo_equip::crates::acl_dsu`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod acl_dsu {pub use self::dsu::*;mod dsu{pub struct Dsu{n:usize,parent_or_size:Vec<i32>,}impl Dsu{pub fn new(size:usize)->Self{Self{n:size,parent_or_size:vec![-1;size],}}pub fn merge(&mut self,a:usize,b:usize)->usize{assert!(a<self.n);assert!(b<self.n);let(mut x,mut y)=(self.leader(a),self.leader(b));if x==y{return x;}if-self.parent_or_size[x]< -self.parent_or_size[y]{std::mem::swap(&mut x,&mut y);}self.parent_or_size[x]+=self.parent_or_size[y];self.parent_or_size[y]=x as i32;x}pub fn same(&mut self,a:usize,b:usize)->bool{assert!(a<self.n);assert!(b<self.n);self.leader(a)==self.leader(b)}pub fn leader(&mut self,a:usize)->usize{assert!(a<self.n);if self.parent_or_size[a]<0{return a;}self.parent_or_size[a]=self.leader(self.parent_or_size[a]as usize)as i32;self.parent_or_size[a]as usize}pub fn size(&mut self,a:usize)->usize{assert!(a<self.n);let x=self.leader(a);-self.parent_or_size[x]as usize}pub fn groups(&mut self)->Vec<Vec<usize>>{let mut leader_buf=vec![0;self.n];let mut group_size=vec![0;self.n];for i in 0..self.n{leader_buf[i]=self.leader(i);group_size[leader_buf[i]]+=1;}let mut result=vec![Vec::new();self.n];for i in 0..self.n{result[i].reserve(group_size[i]);}for i in 0..self.n{result[leader_buf[i]].push(i);}result.into_iter().filter(|x|!x.is_empty()).collect::<Vec<Vec<usize>>>()}}}}
    }

    pub(crate) mod macros {
        pub mod acl_dsu {}
    }

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

    mod preludes {
        pub mod acl_dsu {}
    }
}
0