結果

問題 No.3234 Infinite Propagation
コンテスト
ユーザー urectanc
提出日時 2025-08-15 22:12:23
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 2,623 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,987 ms
コンパイル使用メモリ 397,468 KB
実行使用メモリ 13,460 KB
最終ジャッジ日時 2025-08-15 22:12:47
合計ジャッジ時間 13,218 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;
use std::io::Write;

fn main() {
    let mut writer = std::io::BufWriter::new(std::io::stdout().lock());

    input! { t: usize }

    for _ in 0..t {
        let ans = if solve() { "Yes" } else { "No" };
        writeln!(writer, "{ans}").unwrap();
    }
}

fn solve() -> bool {
    input! {
        n: usize,
        mut pairs: [(String, String); n]
    }
    pairs.sort_unstable();
    pairs.dedup();
    let n = pairs.len();

    let mut dsu = Dsu::new(2 * n + 1);
    let start = 2 * n;
    for i in 0..n {
        dsu.merge(i, n + i);
        if pairs[0].0.contains("a") {
            dsu.merge(i, start);
        }
    }

    for i in 0..n {
        for j in i..n {
            let yi = &pairs[i].1;
            let xj = &pairs[j].0;
            if yi.contains(xj) {
                if dsu.same(j, n + i) && dsu.same(j, start) {
                    return true;
                }
                dsu.merge(j, n + i);
            }
        }
    }

    false
}

pub struct Dsu {
    parent_or_size: Vec<i32>,
}

impl Dsu {
    pub fn new(size: usize) -> Self {
        assert!(size <= i32::MAX as usize);
        Self {
            parent_or_size: vec![-1; size],
        }
    }

    pub fn clear(&mut self) {
        self.parent_or_size.fill(-1);
    }

    pub fn leader(&mut self, u: usize) -> usize {
        if self.parent_or_size[u] < 0 {
            return u;
        }
        self.parent_or_size[u] = self.leader(self.parent_or_size[u] as usize) as i32;
        self.parent_or_size[u] as usize
    }

    pub fn same(&mut self, u: usize, v: usize) -> bool {
        self.leader(u) == self.leader(v)
    }

    pub fn size(&mut self, u: usize) -> usize {
        let x = self.leader(u);
        -self.parent_or_size[x] as usize
    }

    pub fn merge(&mut self, u: usize, v: usize) -> usize {
        let (mut x, mut y) = (self.leader(u), self.leader(v));
        if x == y {
            return x;
        }
        if self.size(x) < self.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 groups(&mut self) -> Vec<Vec<usize>> {
        let n = self.parent_or_size.len();
        let mut result = (0..n)
            .map(|u| {
                let size = if u == self.leader(u) { self.size(u) } else { 0 };
                Vec::with_capacity(size)
            })
            .collect::<Vec<_>>();
        for u in 0..n {
            result[self.leader(u)].push(u);
        }
        result.into_iter().filter(|v| !v.is_empty()).collect()
    }
}
0