結果

問題 No.1266 7 Colors
ユーザー Yukino DX.Yukino DX.
提出日時 2024-09-25 22:15:01
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 218 ms / 3,000 ms
コード長 3,202 bytes
コンパイル時間 13,875 ms
コンパイル使用メモリ 382,868 KB
実行使用メモリ 39,220 KB
最終ジャッジ日時 2024-09-25 22:15:33
合計ジャッジ時間 18,120 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 165 ms
13,952 KB
testcase_04 AC 217 ms
29,824 KB
testcase_05 AC 161 ms
15,232 KB
testcase_06 AC 202 ms
32,512 KB
testcase_07 AC 217 ms
36,224 KB
testcase_08 AC 195 ms
30,592 KB
testcase_09 AC 174 ms
24,960 KB
testcase_10 AC 166 ms
23,296 KB
testcase_11 AC 158 ms
17,280 KB
testcase_12 AC 158 ms
19,200 KB
testcase_13 AC 162 ms
20,992 KB
testcase_14 AC 150 ms
15,104 KB
testcase_15 AC 218 ms
36,864 KB
testcase_16 AC 167 ms
19,584 KB
testcase_17 AC 207 ms
35,264 KB
testcase_18 AC 185 ms
39,220 KB
testcase_19 AC 79 ms
39,168 KB
testcase_20 AC 77 ms
39,040 KB
testcase_21 AC 133 ms
9,216 KB
権限があれば一括ダウンロードができます

ソースコード

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 g=vec![vec![];n];
    for &(u,v) in uv.iter(){
        g[u].push(v);
        g[v].push(u);
    }

    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 g[x].iter(){
                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