競プロ典型90問　ソースコード共有

q059.rs

use fixedbitset::FixedBitSet;
use proconio::{input, fastout, marker::Usize1, };

#[fastout]
fn main() {
    input! {
        n: usize, m: usize, q: usize,
        xy: [(Usize1, Usize1); m],
        ab: [(Usize1, Usize1); q],
    };
    let mut to = vec![vec![]; n];

    for &(x, y) in xy.iter() {
        to[x].push(y);
    }

    for ab_sub in ab.chunks(50000) {
        let mut bitsets = vec![FixedBitSet::with_capacity(50000); n];

        for (i, &(a, _)) in ab_sub.into_iter().enumerate() {
            bitsets[a].set(i, true);
        }

        for x in 0..n {
            for &y in to[x].iter() {
                let (left, right) = bitsets.split_at_mut(y);
                right[0].union_with(&left[x]); 
            }
        }

        for (i, &(_, b)) in ab_sub.into_iter().enumerate() {
            if bitsets[b].contains(i) {
                println!("Yes");
            } else {
                println!("No");
            }
        }
    }
}

q059_u128.rs

use proconio::{input, fastout, marker::Usize1, };

#[fastout]
fn main() {
    input! {
        n: usize, m: usize, q: usize,
        xy: [(Usize1, Usize1); m],
        ab: [(Usize1, Usize1); q],
    };
    let mut to = vec![vec![]; n];

    for &(x, y) in xy.iter() {
        to[x].push(y);
    }

    for ab_sub in ab.chunks(128) {
        let mut bitsets = vec![0u128; n];

        for (i, &(a, _)) in ab_sub.into_iter().enumerate() {
            bitsets[a] |= 1 << i;
        }

        for x in 0..n {
            for &y in to[x].iter() {
                bitsets[y] |= bitsets[x];
            }
        }

        for (i, &(_, b)) in ab_sub.into_iter().enumerate() {
            if bitsets[b] & 1 << i != 0 {
                println!("Yes");
            } else {
                println!("No");
            }
        }
    }
}