結果

問題 No.1266 7 Colors
ユーザー Strorkis
提出日時 2020-10-24 00:41:57
言語 Rust
(1.83.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0