結果

問題 No.1266 7 Colors
ユーザー Yukino DX.Yukino DX.
提出日時 2024-09-25 22:11:37
言語 Rust
(1.77.0 + proconio)
結果
TLE  
実行時間 -
コード長 3,085 bytes
コンパイル時間 16,330 ms
コンパイル使用メモリ 402,548 KB
実行使用メモリ 17,696 KB
最終ジャッジ日時 2024-09-25 22:12:10
合計ジャッジ時間 21,440 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
17,696 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

fn main() {
    input! {
        n:usize,
        m:usize,
        q:usize,
        mut s:[Chars;n],
        uv:[(Usize1,Usize1);m],
        query:[(usize,usize,usize);q],
    }

    let mut uf = UnionFindTree::new(7 * n);
    for i in 0..n {
        for j in 0..7 {
            if s[i][j] == '1' && s[i][(j + 1) % 7] == '1' {
                uf.unite(7 * i + j, 7 * i + (j + 1) % 7);
            }
        }
    }

    for &(u, v) in uv.iter() {
        for i in 0..7 {
            if s[u][i] == '1' && s[v][i] == '1' {
                uf.unite(7 * u + i, 7 * v + i);
            }
        }
    }

    for i in 0..q {
        if query[i].0 == 1 {
            let x = query[i].1 - 1;
            let y = query[i].2 - 1;

            s[x][y] = '1';
            if s[x][(y + 1) % 7] == '1' {
                uf.unite(7 * x + y, 7 * x + (y + 1) % 7);
            }

            if s[x][(7 + y - 1) % 7] == '1' {
                uf.unite(7 * x + y, 7 * x + (7 + y - 1) % 7);
            }

            for j in 0..n {
                if s[j][y] == '1' {
                    uf.unite(7 * x + y, 7 * j + y);
                }
            }
        } else {
            let x = query[i].1 - 1;
            let ans = uf.size(7 * x);
            println!("{}", ans);
        }
    }
}

use unionfindtree::*;
mod unionfindtree {
    pub struct UnionFindTree {
        par: Vec<usize>,
        rank: Vec<usize>,
        size: Vec<usize>,
    }

    impl UnionFindTree {
        pub fn new(n: usize) -> Self {
            Self {
                par: (0..n).collect::<Vec<_>>(),
                rank: vec![0; n],
                size: vec![1; n],
            }
        }

        #[allow(dead_code)]
        pub fn same(&mut self, v1: usize, v2: usize) -> bool {
            self.root(v1) == self.root(v2)
        }

        #[allow(dead_code)]
        pub fn size(&mut self, v: usize) -> usize {
            let v_root = self.root(v);
            self.size[v_root]
        }

        #[allow(dead_code)]
        pub fn root(&mut self, v: usize) -> usize {
            if self.par[v] != v {
                self.par[v] = self.root(self.par[v]);
            }

            self.par[v]
        }

        pub fn unite(&mut self, v1: usize, v2: usize) {
            let mut v1_root = self.root(v1);
            let mut v2_root = self.root(v2);
            if v1_root == v2_root {
                return;
            }

            if self.rank[v1_root] < self.rank[v2_root] {
                std::mem::swap(&mut v1_root, &mut v2_root);
            }

            self.par[v2_root] = v1_root;
            self.size[v1_root] += self.size[v2_root];

            if self.rank[v1_root] == self.rank[v2_root] {
                self.rank[v1_root] += 1;
            }
        }

        #[allow(dead_code)]
        pub fn nofcc(&mut self) -> usize {
            let n = self.par.len();
            (0..n)
                .map(|v| self.root(v))
                .collect::<std::collections::HashSet<usize>>()
                .len()
        }
    }
}
0