bitsetによる64倍高速化

[tipstar0125]

CPU は 64 bit 整数の AND / OR 演算を O(1) で行うことができるので、適切に実装すれば 1 bit の AND / OR 演算は 64 個まとめて行うことができる。

[tipstar0125]

問題：https://mojacoder.app/users/shinnshinn/problems/dep-packages 解答：https://mojacoder.app/users/shinnshinn/problems/dep-packages/submissions/085365c4-25a4-4a80-9381-a4c674b15150

use bitset_fixed::BitSet;

input! {
    N: usize,
    M: usize,
    AB: [(Usize1, Usize1); M]
}

let mut G = vec![vec![]; N];
for &(a, b) in &AB {
    G[b].push(a);
}
let mut bit = vec![BitSet::new(N); N];
for i in 0..N {
    bit[i].set(i, true);
}
for i in (0..N).rev() {
    for &j in &G[i] {
        bit[j] = &bit[i] | &bit[j];
    }
}
for i in 0..N {
    println!("{}", bit[i].count_ones() - 1);
}