結果

問題 No.1266 7 Colors
ユーザー StrorkisStrorkis
提出日時 2020-10-24 00:41:57
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 128 ms / 3,000 ms
コード長 4,235 bytes
コンパイル時間 11,535 ms
コンパイル使用メモリ 395,724 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-07-21 14:29:31
合計ジャッジ時間 14,788 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 70 ms
6,528 KB
testcase_04 AC 113 ms
15,868 KB
testcase_05 AC 73 ms
7,296 KB
testcase_06 AC 120 ms
17,384 KB
testcase_07 AC 128 ms
19,412 KB
testcase_08 AC 103 ms
16,128 KB
testcase_09 AC 94 ms
12,928 KB
testcase_10 AC 87 ms
11,904 KB
testcase_11 AC 74 ms
8,576 KB
testcase_12 AC 80 ms
9,600 KB
testcase_13 AC 86 ms
10,368 KB
testcase_14 AC 72 ms
7,168 KB
testcase_15 AC 124 ms
19,968 KB
testcase_16 AC 81 ms
9,728 KB
testcase_17 AC 128 ms
19,072 KB
testcase_18 AC 78 ms
22,144 KB
testcase_19 AC 76 ms
21,376 KB
testcase_20 AC 76 ms
21,504 KB
testcase_21 AC 27 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::{self, BufRead, Write};
use std::str::FromStr;

struct Dsu {
    n: usize,
    parent_or_size: Vec<usize>,
}

impl Dsu {
    fn new(n: usize) -> Dsu {
        Dsu { n, parent_or_size: vec![!1; n] }
    }

    fn merge(&mut self, a: usize, b: usize) -> usize {
        let (mut x, mut y) = (self.leader(a), self.leader(b));
        if x == y { return x; }
        if !self.parent_or_size[x] < !self.parent_or_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;
        x
    }

    fn leader(&mut self, a: usize) -> usize {
        if self.parent_or_size[a] >= self.n { return a; }
        self.parent_or_size[a] = self.leader(self.parent_or_size[a]);
        self.parent_or_size[a]
    }

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

struct Solver<'a> {
    reader: io::BufReader<io::StdinLock<'a>>,
    writer: io::BufWriter<io::StdoutLock<'a>>,
}

impl Solver<'_> {
    fn read_line(&mut self) -> String {
        let mut input = String::new();
        self.reader.read_line(&mut input).unwrap();
        input
    }

    fn read_triple<T1, T2, T3>(&mut self) -> (T1, T2, T3)
        where T1: FromStr, T2: FromStr, T3: FromStr
    {
        let input = self.read_line();
        let mut iter = input.split_whitespace();
        (
            iter.next().unwrap().parse().ok().unwrap(),
            iter.next().unwrap().parse().ok().unwrap(),
            iter.next().unwrap().parse().ok().unwrap(),
        )
    }

    fn read_char_vec(&mut self) -> Vec<char> {
        let input = self.read_line();
        input.trim_end().chars().collect()
    }

    fn read_char_mat(&mut self, n: usize) -> Vec<Vec<char>> {
        let mut res = Vec::with_capacity(n);
        for _ in 0..n {
            let tmp = self.read_char_vec();
            res.push(tmp);
        }
        res
    }

    fn read_pair<T1: FromStr, T2: FromStr>(&mut self) -> (T1, T2) {
        let input = self.read_line();
        let mut iter = input.split_whitespace();
        (
            iter.next().unwrap().parse().ok().unwrap(),
            iter.next().unwrap().parse().ok().unwrap(),
        )
    }    

    fn writeln<T: std::fmt::Display>(&mut self, ans: T) {
        writeln!(self.writer, "{}", ans).unwrap();
    }

    fn solve(&mut self) {
        let (n, m, q) = self.read_triple::<usize, usize, usize>();
        let mut s = self.read_char_mat(n);

        let mut g = vec![vec![]; n];
        for _ in 0..m {
            let (u, v) = self.read_pair::<usize, usize>();
            let (u, v) = (u - 1, v - 1);
            g[u].push(v);
            g[v].push(u);
        }

        let mut dsu = Dsu::new(n * 7);
        for i in 0..n {
            for j in 0..7 {
                if s[i][j] != '1' { continue; }
                if s[i][(j + 1) % 7] == '1' {
                    dsu.merge(i * 7 + j, i * 7 + (j + 1) % 7);
                }
                for &k in &g[i] {
                    if s[k][j] != '1' { continue; }
                    dsu.merge(i * 7 + j, k * 7 + j);
                }
            }
        }

        for _ in 0..q {
            let (t, x, y) = self.read_triple::<u8, usize, usize>();
            if t == 1 {
                let (x, y) = (x - 1, y - 1);
                s[x][y] = '1';
                if s[x][(y + 6) % 7] == '1' {
                    dsu.merge(x * 7 + y, x * 7 + (y + 6) % 7);
                }
                if s[x][(y + 1) % 7] == '1' {
                    dsu.merge(x * 7 + y, x * 7 + (y + 1) % 7);
                }
                for &z in &g[x] {
                    if s[z][y] != '1' { continue; }
                    dsu.merge(x * 7 + y, z * 7 + y);
                }
            } else {
                let x = x - 1;
                self.writeln(dsu.size(x * 7));
            }
        }
    }

    fn run() {
        let (stdin, stdout) = (io::stdin(), io::stdout());
        let reader = io::BufReader::new(stdin.lock());
        let writer = io::BufWriter::new(stdout.lock());
        let mut solver = Solver { reader, writer };
        solver.solve();
    }
}

fn main() {
    Solver::run();
}
0