結果

問題 No.1266 7 Colors
ユーザー StrorkisStrorkis
提出日時 2020-10-24 00:31:22
言語 Rust
(1.77.0 + proconio)
結果
RE  
実行時間 -
コード長 4,235 bytes
コンパイル時間 15,554 ms
コンパイル使用メモリ 378,704 KB
実行使用メモリ 22,272 KB
最終ジャッジ日時 2024-07-21 14:23:05
合計ジャッジ時間 17,403 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
権限があれば一括ダウンロードができます

ソースコード

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(7 * n);
        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 * n + j, i * n + (j + 1) % 7);
                }
                for &k in &g[i] {
                    if s[k][j] != '1' { continue; }
                    dsu.merge(i * n + j, k * n + 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 * n + y, x * n + (y + 6) % 7);
                }
                if s[x][(y + 1) % 7] == '1' {
                    dsu.merge(x * n + y, x * n + (y + 1) % 7);
                }
                for &z in &g[x] {
                    if s[z][y] != '1' { continue; }
                    dsu.merge(x * n + y, z * n + y);
                }
            } else {
                let x = x - 1;
                self.writeln(dsu.size(x * n));
            }
        }
    }

    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